HDU 5750 BestCoder Round #84 Dertouzos （素数筛选）

HDU 5750 BestCoder Round #84 Dertouzos （素数筛选）

Dertouzos

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1518    Accepted Submission(s): 484

Problem Description

A positive proper divisor is a positive divisor of a number n, excluding 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 and d. He would like to know the number of integers below n whose maximum positive proper divisor is d.

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤106), indicating the number of test cases. For each test case: The first line contains two integers n and d (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

Source

​​BestCoder Round #84​​

Recommend

wange2014   |   We have carefully selected several similar problems for you:  ​​5751​​​ ​​5746​​​ ​​5745​​​ ​​5744​​​ ​​5743​​

题解：给你 t 个 n 和 d ，让你求小于n的数中最大约数（不包括本身）为d的数量。

因为要使最大因数为d，必存在x*d=m，同时x必须为质数，且x必须小于d的最小质因数，因此找n前面有几个m成立即可。因为 t 范围很大，所以可以先打表筛选出质数表再线性扫一遍就可以了。

AC代码：

//#include#include#include#include#include#include#includeusing namespace std;int isprime[100005]={0};int prime[100005]={0};int k=0;int init(){ int i,j; for(i=2;i<100000;i++) { if(isprime[i]==0) { for(j=2;i*j<100000;j++) isprime[i*j]=1; prime[k]=i; k++; } } return 0;}int main(){ int t,i; int m,n; scanf("%d",&t); init(); while(t--) { scanf("%d%d",&m,&n); for(i=0;i=m) break; if(n=m || n

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。