本文主要是介绍C - Dertouzos (HDU 5750)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
VJ上的链接：https://cn.vjudge.net/problem/HDU-5750
题目大意：给定n和d，求1~(n-1)里面最大约数为d的数有多少个(d除外)
思路：因为d是最大约数，所以n=最小质因子*d，记minpf(n)是n的最小质因子，则我们取出的数一定要小于等于minpf(d)，否则一定可以从d中分解出比取出来的数更小的因子
ps：c++用cin会超时。。。换成scanf，记得加上cstdio
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;const int tomax=40000;
long long np[tomax],prime[tomax];
int cont;void initialize() //打素数表，保存在prime里
{memset(np,0,sizeof(np));cont=0;for(long long i=2; i<tomax; i++)if(np[i]==0){prime[cont]=i;cont++;for(long long j=i*i; j<tomax; j+=i)np[j]=1;}
}long long solve(long long n,long long d)
{long long ans=0;for(int i=0;i<cont;i++){if(d*prime[i]>=n) break;ans++;if(d%prime[i]==0) break;}return ans;
}
int main()
{int t;long long n,d,ans;initialize();scanf("%d",&t);for(int i=0;i<t;i++){scanf("%lld %lld",&n,&d);ans=solve(n,d);cout<<ans<<endl;}return 0;
}
这篇关于C - Dertouzos (HDU 5750)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
