www.codechef.com/MAY15/problems/CHAPD

一道比较神奇的题目...

看到题目后自己yy出了个傻逼算法...然后对拍都是对的...提交都是错的...然后一看"Yes"打成"YES"了...= =!!人傻逼就是会犯脑残错误...

我的算法是$O\left(\log^2{n}\right)$的,但是实践中跑得很快...

这道题需要不多的数论知识= =...

我们设pf(x)={p|primes(p),p|x}

显然题目要求你判断$\mathtt{pf}(B)\subseteq \mathtt{pf}(A)$.

然后是比较奇怪的想法...我一开始就想到了,问了问LZW学长但是他没想到...

那么我们要判断的是$\mathtt{pf}\left(\gcd{A,B}\right)=\mathtt{pf}\left(B\right)$

我们记$C=\gcd{A,B}$

那么上面命题成立的充分必要条件是$\mathtt{pf}\left(\frac{B}{C}\right)\subseteq \mathtt{pf}\left(C\right)$

这个证明就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\n"); else printf("No\n");

	}

	return 0;

}