题目链接：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的参数需要是浮点数
1 #include2 #include 3 #include 4 using namespace std; 5 #define LL long long 6 7 LL gcd(LL a,LL b) 8 { 9 if (b==0) return a;10 return gcd(b,a%b);11 }12 13 int T;14 LL n,m;15 int main()16 {17 scanf("%d",&T);18 while (T--)19 {20 //scanf("%lld%lld",&n,&m);21 cin>>n>>m;22 //gcd=n lcm=m23 if (m%n!=0)24 printf("0\n");25 else26 {27 LL ans=0;28 LL N=m/n;29 LL i,Tm;30 LL T=sqrt(N*1.0);31 for (i=1;i<=T;i++)32 {33 if (N%i==0)34 {35 Tm=N/i;36 if (gcd(Tm,i)==1)37 ans++;38 }39 }40 cout< <
O
很水的找规律题啦~
1 #include2 #include 3 using namespace std; 4 5 long long N,M,tm; 6 7 int main() 8 { 9 while(~scanf("%lld",&N))10 {11 M=N/3;12 tm=N%3; //0,1,213 M=M*2;14 if (tm==2) M++;15 printf("%lld\n",M);16 }17 return 0;18 }