www.codechef.com/MAY15/problems/CHAPD
一道比较神奇的题目...
看到题目后自己yy出了个傻逼算法...然后对拍都是对的...提交都是错的...然后一看"Yes"打成"YES"了...= =!!人傻逼就是会犯脑残错误...
我的算法是$Oleft(log^2{n} ight)$的,但是实践中跑得很快...
这道题需要不多的数论知识= =...
我们设pf(x)={p|primes(p),p|x}
显然题目要求你判断$mathtt{pf}(B)subseteq mathtt{pf}(A)$.
然后是比较奇怪的想法...我一开始就想到了,问了问LZW学长但是他没想到...
那么我们要判断的是$mathtt{pf}left(gcd{A,B} ight)=mathtt{pf}left(B ight)$
我们记$C=gcd{A,B}$
那么上面命题成立的充分必要条件是$mathtt{pf}left(frac{B}{C} ight)subseteq mathtt{pf}left(C ight)$
这个证明就yy一下好了,感觉挺好证的..
那么就可以递归求解了...
代码
#include <cstdio>
typedef long long ull;
ull a,b;
ull gcd(ull a,ull b){
return a?gcd(b%a,a):b;
}
bool isk(ull a,ull b){
ull c=gcd(a,b);
ull d=b/c;
if(c==1&&d!=1) return false;
if(d!=1ll) return isk(c,d);
return true;
}
int T;
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&a,&b);
if(isk(a,b)) printf("Yes
"); else printf("No
");
}
return 0;
}