题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5750

Dertouzos

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2172    Accepted Submission(s): 672    Problem Description

A positive proper divisor is a positive divisor of a number  n n, excluding  n n itself. For example, 1, 2, and 3 are positive proper divisors of 6, but 6 itself is not.  Peter has two positive integers  n n and  d d. He would like to know the number of integers below  n n whose maximum positive proper divisor is  d d. Input There are multiple test cases. The first line of input contains an integer  T T  (1≤T≤106) (1≤T≤106), indicating the number of test cases. For each test case:  The first line contains two integers  n n and  d d  (2≤n,d≤109) (2≤n,d≤109). Output For each test case, output an integer denoting the answer.  Sample Input 9 10 2 10 3 10 4 10 5 10 6 10 7 10 8 10 9 100 13 Sample Output 1 2 1 0 0 0 0 0 4

题意：为你一个n和一个d；在2到n中找出一些数，例如6，它有因子2，3（因子除了1和它本身，下同）;所以6的最大因子是3，

现在在2到n中找出一些数，这些数的最大因子是d；求这些数有多少个；

思路：假设一个数为a，使得d*a<n；如果a不是素数的话，a总是有一个因子b，使得b*d>d，即a*d的因子b*d比因子d大，所以a*d一定不符合条件，如果a>d&&d*a<n，a*d也一定不符合条件,因为a比d大;如果a比d的其中一个因子大，就可以替换那个因子得到比d大的数字，所以当d%a==0；时说明比a大的素数一定不行，直接break；

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<map> #include<string> #define LL long long int #define inf 0x3f3f3f3f #define N 100010 #define mod 10000007 using namespace std; bool a[50100]={0}; int b[10000]; int main() { int sum=0; for(int i=2;i<=50000;i++) { if(!a[i]) { for(int j=i*2;j<=50000;j+=i) a[j]=1; b[sum++]=i; } } int t; scanf("%d",&t); while(t--) { int n,d; int ans=0; scanf("%d%d",&n,&d); for(int i=0;b[i]*d<n&&b[i]<=d;i++) { ans++; if(d%b[i]==0) break; } printf("%d\n",ans); } }