首页 > 其他 > 详细

hdu 5750(数论)

时间:2016-07-24 12:06:02      阅读:246      评论:0      收藏:0      [点我收藏+]

Dertouzos

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


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 (1T106), indicating the number of test cases. For each test case:

The first line contains two integers n and d (2n,d109).
 

 

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
 
 
题意:如果 d 是k除了自身以外最大的因子, 在[2,n)内找有多少个数满足 最大的因子是 k .
题解:昨天想得太简单了,真是naive..我开始的想法是 将 min(d,(n-1)/d) 里面所有的质数算出来,然后天真的以为这就是结果...然后一直WA,忽视了一个很重要的条件,那就是我们的数中d一定是最大的因子,所以如果出现了能够将d整除的质数,那么我们就可以将d分解,从而得到一个更大的 d‘ ,所以说我们选择的质数是不能够将 d 除尽的.
#include<iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 100005;
bool p[N];
int prime[N];
int id;
void init()
{
    id = 0;
    for(int i=2; i<N; i++)
    {
        if(!p[i])
        {
            prime[++id] = i;
            for(LL j=(LL)i*i; j<N; j+=i)
            {
                p[j] = true;
            }
        }
    }
}

int main()
{
    init();
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        int n,d;
        scanf("%d%d",&n,&d);
        int ans = 0;
        for(int i=1; i<=id; i++)
        {
            if(prime[i]*d>=n) break;
            ans++;
            if(d%prime[i]==0) break;
        }
        printf("%d\n",ans);
    }
    return 0;
}

 

hdu 5750(数论)

原文:http://www.cnblogs.com/liyinggang/p/5700292.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!