Codeforces 371B Fox Dividing Cheese(简单数论)

思路：求出两个数a和b的最大公约数g，然后求出a/g，b/g，分别记为c和d。

　　　然后考虑c和d，若c或d中存在不为2,3,5的质因子，则直接输出-1(根据题目要求)

计算出c = (2 ^ a2) * (3 ^ a3) * (5 ^ a5) d = (2 ^ b2) * (3 ^ b3) * (5 ^ b5)

　　　那么答案就是a2 + a3 + a5 + b2 + b3 + b5

#include <bits/stdc++.h>

using namespace std;

int a, b;

int n, m, x;

int a2, a3, a5, b2, b3, b5;

int gcd(int a, int b){

    return b ==  ? a : gcd(b, a % b);

}

int main(){

    scanf("%d%d", &n, &m);

    if (n == m){puts(""); return ;}

    x = gcd(n, m);

    a = n / x, b = m / x;

    while (a %  == ) { a /= , ++a2;}

    while (a %  == ) { a /= , ++a3;}

    while (a %  == ) { a /= , ++a5;}

    while (b %  == ) { b /= , ++b2;}

    while (b %  == ) { b /= , ++b3;}

    while (b %  == ) { b /= , ++b5;}

    if (a >  || b > ){

        puts("-1");

        return ;

    }

    printf("%d\n", a2 + a3 + a5 + b2 + b3 + b5);

    return ;

}

巴特西

Codeforces 371B Fox Dividing Cheese(简单数论)

最新文章

热门文章