Codeforces Round #218 (Div. 2) B. Fox Dividing Cheese(思维 数学)

xiaoxiao2021-02-28  166

题意:给你两个数a b,每次操作可以将某个数整除2 或 整除3 或 整除5,问最少操作多少次可以使两个数相等,不能的话输出-1.

思路:

两个数可以看作

a = x * pow(2, m1) * pow(3, m2) * pow(5, m3)

b = y * pow(2, n1) * pow(3, n2) * pow(5, n3)

要使两个数相等,x和y必须相同,x和y相同的条件下怎样操作次数最小呢?就是2 3 5指数都靠近小的那个就行了,abs(m1-n1)+abs(m2-n2)+abs(m3-n3).

#include<bits/stdc++.h> using namespace std; int a, b, ans; void cal(int x) { int c1 = 0, c2 = 0; while(!(a%x)) a /= x, c1++; while(!(b%x)) b /= x, c2++; ans += abs(c1-c2); } int main(void) { while(cin >> a >> b) { ans = 0; cal(2), cal(3), cal(5); if(a != b) puts("-1"); else printf("%d\n", ans); } return 0; }

转载请注明原文地址: https://www.6miu.com/read-60608.html

最新回复(0)