codeforces 490D Chocolate 數論
傳送門:cf 490D
有兩個矩形,現在可以對矩形作兩種操作。
(1)將矩形去掉一半(某一邊變為原來的一半,要求該邊可以被2整除)
(2)將矩形去掉三分之一(某一邊變為原來的三分之二,要求該邊能被3整除)
問最少進行多少次操作可以使得兩個矩形的面積相同,並分別輸出操作之後的兩個矩形的邊長
可以發現,兩種操作等價於去掉一個素因子2,或者把一個素因子3變成一個素因子2,對其他的素因子不會產生影響,因此首先把剔除2,3的素因子,判斷剩余的素因子集合的乘積是否相等,若不相等則無法通過操作使得乘積相等。
然後使得記錄使得素因子3和2相等
/******************************************************
* File Name: d.cpp
* Author: kojimai
* Create Time: 2014年11月23日 星期日 18時23分21秒
******************************************************/
#include
#include
#include
#include
#include
using namespace std;
int cnt2[5];
int cnt3[5];
int main()
{
long long x1,y1,x2,y2;
cin>>x1>>x2;
cin>>y1>>y2;
long long t1 = x1,t2 = x2,k1 = y1,k2 = y2;
memset(cnt2,0,sizeof(cnt2));
memset(cnt3,0,sizeof(cnt3));
while(t1 % 2==0)
{
t1 /= 2;
cnt2[0]++;
}
while(t1 % 3==0)
{
t1 /= 3;
cnt3[0]++;
}
while(t2 % 2==0)
{
t2 /= 2;
cnt2[1]++;
}
while(t2 % 3==0)
{
t2 /= 3;
cnt3[1]++;
}
while(k1 % 2==0)
{
k1 /= 2;
cnt2[2]++;
}
while(k1 % 3==0)
{
k1 /= 3;
cnt3[2]++;
}
while(k2 % 2==0)
{
k2 /= 2;
cnt2[3]++;
}
while(k2 % 3==0)
{
k2 /= 3;
cnt3[3]++;
}
//分別記錄下四條邊中素因子2,3的個數
if(t1 * t2 != k1 * k2)//剩余的素因子的乘積不等
cout<<-1< y3)
{
xd3 = x3 - y3;
x4 += xd3;//每去掉一個素因子3就對應需要增加一個素因子2
ans += xd3;
}
else if(x3 < y3)
{
yd3 = y3 - x3;
y4 += yd3;
ans += yd3;
}
//對素因子3操作使得3的個數相等
if(x4 > y4)
{
xd4 = x4 - y4;
ans += xd4;
}
else if(x4 < y4)
{
yd4 = y4 - x4;
ans += yd4;
}
//對素因子2操作使得2的個數相等
printf("%d\n",ans);
if(xd3)//需要對第一個矩形進行去三分之一的操作
{
while(x1 % 3 == 0 && xd3)
{
x1 = x1 / 3 * 2;
xd3--;
}
while(x2 % 3 == 0 && xd3)
{
x2 = x2 /3 * 2;
xd3--;
}
}
if(xd4)//需要對第一個矩形進行去二分之一的操作
{
while(x1 % 2 == 0 && xd4)
{
x1 = x1 / 2;
xd4--;
}
while(x2 % 2 == 0 && xd4)
{
x2 /= 2;
xd4--;
}
}
if(yd3)//需要對第二個矩形進行去三分之一的操作
{
while(y1 % 3 == 0 && yd3)
{
y1 = y1/3*2;
yd3--;
}
while(y2 % 3 == 0 && yd3)
{
y2 = y2/3*2;
yd3--;
}
}
if(yd4)//需要對第二個矩形進行去二分之一的操作
{
while(y1 % 2 == 0 && yd4)
{
y1 = y1 / 2;
yd4--;
}
while(y2 % 2 == 0 && yd4)
{
y2 /= 2;
yd4--;
}
}
cout<
需要的操作數,並對應修改邊的長度即可
