标签: 模拟 - CheaSim Blog

[hdoj5505]GT and numbers

GT and numbers

题意

题目意思比较绕,就是给定一个$N$和$M$问至少要多少次下列的操作可以使得$N$等于$M$。

  • 将N乘上一个它的因子(注意$N$也会变)。

题解

由于我们要求$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;
//head
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;
}