hud 5750 Dertouzos

Dertouzos

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

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

 

一：直接暴力，这种方法是存在缺点的，可能会被卡数据。

#include<iostream>

#include<stdio.h>

using namespace std;

const int maxx=;

bool flag[maxx];

int prime[maxx];

int main(){

    int cnt=;

    for(int i=;i<maxx;i++){

        if(!flag[i]){

            for(int j=i<<;j<maxx;j+=i){

                flag[j]=;

            }

            prime[cnt++]=i;

        }

    }

//    for(int i=0;i<100;i++) cout<<prime[i]<<endl;

    int t;

    scanf("%d",&t);

    int n,d;

    while(t--){

        scanf("%d%d",&n,&d);

        int ans=;

        for(int i=;i<=cnt-&&prime[i]<=d&&prime[i]*d<n;i++){

            if(d%prime[ans]==){

                break;

            }

            ans++;

        }

        if(prime[ans]>d||prime[ans]*d>=n);

        else ans++;

        printf("%d\n",ans);

    }

    return ;

}

二、官方题解

Dertouzos

随便推导下, 令y=xdy=xd, 如果dd是yy的maximum positive proper divisor, 显然要求xx是yy的最小质因子. 令mp(n)mp(n)表示nn的最小质因子, 那么就有x \le mp(d)x≤mp(d), 同时有y < ny<n, 那么x \le \lfloor \frac{n-1}{d} \rfloorx≤⌊​d​​n−1​​⌋. 于是就是计算有多少个素数xx满足x \le \min{mp(d), \lfloor \frac{n-1}{d} \rfloor}x≤min{mp(d),⌊​d​​n−1​​⌋}.

当dd比较大的时候, \lfloor \frac{n-1}{d} \rfloor⌊​d​​n−1​​⌋比较小, 暴力枚举xx即可. 当dd比较小的时候, 可以直接预处理出答案. 阈值设置到10^6 \sim 10^710​6​​∼10​7​​都可以过.