CF490D Chocolate 题解

FFTotoro · 2022-12-14 21:48:23 · 题解

看到楼上一堆大分讨，本人觉得完全没有必要。

本题可以使用一些数论的技巧。

记 f(n,i)（其中 i\in\{2,3\}）为正整数 n 分解质因数的形式中包含 i 的个数，那么需要满足最终条件，即为满足 f(a,2)+f(b,2)=f(c,2)+f(d,2) 且 f(a,3)+f(b,3)=f(c,3)+f(d,3)。将此记为条件 P。

然后考虑每一轮操作，如果 f(a,i)+f(b,i)>f(c,i)+f(d,i)，那么，取 a 和 b 中分解质因数包含 i 的一个（如果都包含就任取一个），不妨设为 a，然后 a\leftarrow \frac{a(i-1)}{i}；反之，类似地 c 和 d 也可以按上面的操作一步步完成。

最终，满足 P 之后就可以判断，ab 是否与 cd 相等。如果相等就输出，不相等就判误解。可以证明，先处理 i=3，再处理 i=2，这种操作方式就不会有任何的冗余，所以它就是操作数最少的。

放代码：

#include<bits/stdc++.h>
using namespace std;
int f(int n,int i){
  return n%i?0:1+f(n/i,i);
}
int main(){
  int a,b,c,d,s=0; cin>>a>>b>>c>>d;
  for(int i=3;i>=2;i--)
    while(f(a,i)+f(b,i)-f(c,i)-f(d,i)&&++s){
      if(f(a,i)+f(b,i)>f(c,i)+f(d,i)){
        if(f(a,i))a=a/i*(i-1);
        else b=b/i*(i-1);
      }
      else{
        if(f(c,i))c=c/i*(i-1);
        else d=d/i*(i-1);
      }
    }
  if(1ll*a*b!=1ll*c*d)cout<<"-1\n";
  else cout<<s<<endl<<a<<' '<<b<<endl<<c<<' '<<d<<endl;
  return 0;
}