[原创]BestCoder Round #84 &&HDU 5750 Dertouzos 【数论+暴力】

2016-07-23 23:14:02 Tabris_ 阅读数：871

博客爬取于2020-06-14 22:44:07
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52008038

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

-----------------------------------------.

Dertouzos Accepts: 76 Submissions: 1357
Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
问题描述
正整数xx称为nn的positive proper divisor, 当且仅当x∣nx | n并且1≤x<n1 \le x < n. 例如, 1, 2, 和3是6的positive proper divisor, 但是6不是.

Peter给你两个正整数nn和dd. 他想要知道有多少小于nn的整数, 满足他们的最大positive proper divisor恰好是dd.
输入描述
输入包含多组数据, 第一行包含一个整数T(1≤T≤106)T (1 \le T \le 10^6)表示测试数据组数. 对于每组数据:

第一行包含两个整数nn和dd$ (2 \le n, d \le 10^9)$

输出描述
对于每组数据, 输出一个整数.
输入样例
9
10 2
10 3
10 4
10 5
10 6
10 7
10 8
10 9
100 13
输出样例
1
2
1
0
0
0
0
0
4

----------------------------------------------------.

题目大意： 自己看

解题思路：
首先要明确的是 NM的最大因子为N的时候只有M为素数 且M<=N的最小素因子的时候 ；
试想 $N=p_1^{a_1}p_2^{a_2}p_3^{a_3}p_4^{a_4} …… p_n^{a_n} ; (p[i] < p[i+1]) $
如果M不是素数那么M=XY，NM的因子中 就多了NX和NY 均比N大 所以不成立
如果M>p1 （假设所有的ai均为1）那么N*M的因子中 就多了M∗p2∗p3∗p4∗……∗pnM * p_2 * p_3 * p_4 * …… *p_n 一定大于p1∗p2∗p3∗p4∗……∗pnp_1 * p_2 * p_3 * p_4 * …… *p_n 所以也不成立 至于某个ai>1a_i>1的时候同理
也不行

所以先打出sqrt(1e9)内的所有素数
然后暴力找即可

1
2
3
4
5
6
for(int i=0;i<k;i++)
 {
     if(d*prime[i]>=n)   break;
     sum++;
     if(d%prime[i]==0)   break;
 }

k值不到1e4 加上题目3500ms 就能过了

附上本题代码

----------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <iostream>
# include <algorithm>
# include <cmath>
# include <cstdio>
# include <cstring>
using namespace std;

# define LL __int64

const LL MOD = 1e9+7;
const LL INF = 0x3f3f3f3f;

int Is_or[101010];
int prime[10000];
int k=0;

void Prime()
{
    memset(Is_or,1,sizeof(Is_or));

    int n=100000;
    for(int i=2;i<=n;i++)
        if(Is_or[i])
        {
            prime[k++]=i;
            for(int j=i+i;j<=n;j+=i)
                Is_or[j]=0;
        }

    return ;
}

int primeproper(int num,int n)
{
    int sum=0;
    for(int i=0;i<k;i++)
    {
        if(num*prime[i]>=n)   break;
        sum++;
        if(num%prime[i]==0)   break;
    }
    return sum;
}

int main()
{
    Prime();
    printf("%d  %d  ",prime[k-1],prime[4229]);
    printf("%d\n",k);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);

        int d = primeproper(m,n);

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

    }
    return 0;
}