题目链接：http://4.gdutcode.sinaapp.com/contest.php?cid=1021
F
题意：给出n和m，要求满足gcd(x,y)=n && lcm(x,y)=m的pair(x,y)的个数
sol：先YY一下：
设 gcd(x,y)=n，lcm(x,y)=m
那么有x=a*n，y=b*n ； m=c*x，m=d*y （其中a与b互质，c与d互质）
那么有m=a*c*n，m=b*d*n
又因为a、b、c、d必须是整数，所以m/n必须是整数，即m%n==0 //(不用纠结。。。这条性质是确定的)
设N=m/n，那么有a*c=b*d=N （其中a与b互质，c与d互质）
这里会有一个奇怪的事实：要想满足这个条件，那么a与c互质，b与d互质
证明自己想去。。。。。。（逃
证明：设a有质因子AA，那么b一定没有质因子AA
又因为ac=bd，所以d必须有质因子AA
又因为c和d互质，所以c一定没有质因子AA
所以a有的质因子c一定不能有。所以a与c互质。
同理可证b和d互质
这时问题就转化成了：在N的所有约数中，找出所有互质的pair。
O(sqrt(N))就可以搞定~
在coding的时候注意一个地方：
LL T=sqrt(N*1.0);
那个1.0是必须要乘的，因为sqrt的参数需要是浮点数
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define LL long long LL gcd(LL a,LL b)
{
if (b==) return a;
return gcd(b,a%b);
} int T;
LL n,m;
int main()
{
scanf("%d",&T);
while (T--)
{
//scanf("%lld%lld",&n,&m);
cin>>n>>m;
//gcd=n lcm=m
if (m%n!=)
printf("0\n");
else
{
LL ans=;
LL N=m/n;
LL i,Tm;
LL T=sqrt(N*1.0);
for (i=;i<=T;i++)
{
if (N%i==)
{
Tm=N/i;
if (gcd(Tm,i)==)
ans++;
}
}
cout<<ans<<endl;
}
} return ;
}
O
很水的找规律题啦~
#include <iostream>
#include <cstdio>
using namespace std; long long N,M,tm; int main()
{
while(~scanf("%lld",&N))
{
M=N/;
tm=N%; //0,1,2
M=M*;
if (tm==) M++;
printf("%lld\n",M);
}
return ;
}