【*1700质因子分解】CF1538D

た入场券 2024-03-22 20:16 65阅读 0赞

[Problem - D - Codeforces][]

题意：

给定两个数a和b，每次操作可以在两个数中选一个数然后除它的一个因子，问你是否可以进行正好K次操作之后a和b相同

![da3cbd268c824f7f9d957b6119c258c0.png][]

![36f4d8e1b99c45a8aa15199a7cef02ba.png][]

思路：

可以模拟一下小样例：

36=2^2\*3^2

48=2^4\*3^1

可以发现，最多操作次数是(2+2+4+1)

最少操作次数呢？那就是变成a和b的gcd的次数

设最大次数为max，最少次数为min

然后可以发现，我们可以操作\[min,max\]内的任意次数（这个稍微想一下即可）

因此就变成判断max<=K了

对于K=1的情况需要特判

Code：

#include <bits/stdc++.h>
     
    #define int long long
     
    using namespace std;
     
    const int mxn=1e5+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N,a,b,k;
    int len=0;
    int prime[mxn],vis[mxn];
    
    int calc(int x){
    	int res=0;
    	for(int i=1;i<=len;i++){
    		int p=prime[i];
    		if(x%p==0){
    			while(x%p==0){
    				x/=p;
    				res++;
    			}
    		}
    	}
    	if(x!=1) res++;
    	return res;
    }
    void P_init(int n){
    	for(int i=2;i<=n;i++){
    		if(!vis[i]) prime[++len]=i;
    		for(int j=1;i<=n/prime[j];j++){
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0) break;
    		}
    	}
    }
    void solve(){
    	cin>>a>>b>>k;
    	if(k==1){
    		if(a==b){
    			cout<<"NO"<<'\n';
    			return;
    		}else if(a%b==0||b%a==0){
    			cout<<"YES"<<'\n';
    			return;
    		}else{
    			cout<<"NO"<<'\n';
    			return;
    		}
    	}
    	if(calc(a)+calc(b)>=k) cout<<"YES"<<'\n';
    	else cout<<"NO"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        P_init(1e5);
        while(__--)solve();return 0;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1538/problem/D
[da3cbd268c824f7f9d957b6119c258c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/7b1cc9fd87a448d980383bf4281e76fe.png
[36f4d8e1b99c45a8aa15199a7cef02ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/01ab0555646049dab9408e90934bbeca.png