HDU 3353
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
http://acm.hdu.edu.cn/showproblem.php?pid=3353
题目其实就是要把A B分解质因数，X是它们质因数的并集，D是质因数指数的和（如果有相同的质因数，把它们的指数做减法求绝对值）
水题，wa了好多次，手抖最后把while敲成if...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <set> using namespace std; int a[],ac[],b[],bc[]; int ABS(int x){
return x>?x:-x;
} int main(){
int A,B;
int cas=;
while(~scanf("%d%d",&A,&B)){
if(!A && !B)break;
int st1,st2;
st1=st2=;
memset(ac,,sizeof(ac));
memset(bc,,sizeof(bc));
for(int i=;i*i<=A;i++){
if(A%i==){
a[st1]=i;
while(A%i==){
ac[st1]++;
A/=i;
}
st1++;
}
}
if(A>){
a[st1]=A;
ac[st1++]=;
}
for(int i=;i*i<=B;i++){
if(B%i==){
b[st2]=i;
while(B%i==){
bc[st2]++;
B/=i;
}
st2++;
}
}
if(B>){
b[st2]=B;
bc[st2++]=;
}
int i,j;
i=j=;
int X,D;
X=D=;
while(i<st1 && j<st2){
if(a[i]==b[j]){
X++;
D+=ABS(ac[i]-bc[j]);
i++;j++;
}
else if(a[i]<b[j]){
X++;
D+=ac[i];
i++;
}
else{
X++;
D+=bc[j];
j++;
}
}
while(i==st1 && j<st2){
X++;
D+=bc[j];
j++;
}
while(j==st2 && i<st1){
X++;
D+=ac[i];
i++;
}
printf("%d. %d:%d\n",cas++,X,D);
}
return ;
}
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |