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

Tabris

CSDN数学

发布于：2016年7月23日

次浏览

[原创]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)
问题描述
正整数x称为n的 positive proper divisor, 当且仅当x | n并且 $1 \le x < n$. 例如， 1, 2, 和 3 是 6 的 positive proper divisor, 但是 6 不是。

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

第一行包含两个整数n和d (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 * p_2 * p_3 * p_4 * …… *p_n 一定大于 p_1 * p_2 * p_3 * p_4 * …… *p_n 所以也不成立 至于某个a_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;
}

本页文档最后更新于：2021年5月16日

CSDN