GT and numbers
题意
题目意思比较绕,就是给定一个$N$和$M$问至少要多少次下列的操作可以使得$N$等于$M$。
题解
由于我们要求$N$转化成$M$,那么其实就是他们的素因子变成相同。
$N = 2^{a_1} * 3^{a_2}5^{a_3}…$
$M = 2^{b_1}*3^{b_2}5^{b_3}…$
那么我们就可以看出 如果要让$a_1=b_1,a_2=b_2,a_3=b_3…$我们需要在他们差距最大的那个素因子中他们相差的倍数的。
$log_2(倍数)$
tip 由于2e63 爆了long long 。所以要用unsigned long long。
ac代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| #include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=(a);i<(n);i++) #define per(i,a,n) for(int i=(n-1);i>=(a);i--) #define fi first #define se second typedef pair <int,int> pII; typedef unsigned long long ll; const int INF = 0x3f3f3f3f;
ll n,m;
int prime[1100000],primesize,phi[11000000]; bool isprime[11000000]; void getlist(int listsize) { memset(isprime,1,sizeof(isprime)); isprime[1]=false; for(int i=2;i<=listsize;i++) { if(isprime[i])prime[++primesize]=i; for(int j=1;j<=primesize&&i*prime[j]<=listsize;j++) { isprime[i*prime[j]]=false; if(i%prime[j]==0)break; } } } int main(){ #ifdef LOCAL freopen("1.in","r",stdin); #endif int T; scanf("%d",&T); getlist(4000000); while(T--){ scanf("%llu%llu",&n,&m); ll ans = 0; bool flag = false; for(ll i=1;prime[i]<=n;i++){ ll cnt1= 0,cnt2 = 0; ll t = prime[i]; while(n%t==0) n/=t,cnt1++; while(m%t==0 && m) m/=t,cnt2++; if(cnt1>cnt2 ||(cnt1==0 && cnt2>0)){ flag = true; break; } if(cnt1 == 0) continue; ll temp = cnt2/cnt1; if(temp*cnt1<cnt2) temp++; ans = max(temp,ans); } if(m>1) flag = true; if((n==1 && n!=m) || flag){ puts("-1"); }else{ if(ans==0){ puts("0"); continue; } ll temp = 1; int res = 0; while(temp<ans) temp<<=1,res++; printf("%d\n",res); } } return 0; }
|