找出N的所有大于等于M的因子(x1,x2,x3.....xi),然后设k=N/xi;
下面只需找出小于k且与k互质的数。
因为:设y与k互质且小于k,那么gcd(y*xi,k*xi)=xi;(xi为N的因子,且xi大于等于M)。
#include<iostream>
using namespace std;
int M,N;
int ans;
inline int eular(int x)
{
int ret=x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
{
ret=ret/i*(i-1);
while(x%i==0)
{
x/=i;
}
}
}
if(x>1)
ret=ret/x*(x-1);
return ret;
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>N>>M;
ans=0;
for(int i=1;i*i<=N;i++)
{
if(N%i==0)
{
if(i>=M)
ans+=eular(N/i);
if(i!=N/i)
{
if(N/i>=M)
ans+=eular(i);
}
}
}
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
算法-欧拉回路(HDU-1878)(包含源程序).rar
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦