Решение задачи Как лисица сыр делила с Codeforces

Без пояснения   Просмотров: 351


Два жадных медвежонка нашли в лесу два куска сыра массами a и b грамм, соответственно. Медвежата настолько жадные, что готовы набить друг другу шишек за право обладания куском побольше. Подскакивает к ним лисица и говорит: «Погодите, медвежата, я могу помочь вам уравнять куски!» «Да ладно, как же ты это сделаешь?», — поинтересовались медвежата. «Очень просто — сказала лисица. — Если масса какого-то куска делится на два, то я могу откусить от него ровно половину и съесть. Если масса какого-то куска делится на три, то я могу откусить от него ровно две трети, а если масса делится на пять — то могу откусить и съесть четыре пятых. Вот немного пооткусываю, и уравняю куски».

Код

#include <bits\stdc++.h>
using namespace std;
int a,b,res;
void check(int x)
{
	int z=0,y=0;
	while(a%x==0){ a/=x; z++; }
	while(b%x==0){ b/=x; y++; }
	res+=abs(z-y);
}
int main(void)
{
	cin>>a>>b;
	check(2),check(3),check(5);
	if(a!=b)
		cout<<-1;
	else
		cout<<res;
}

         

Администратор Photo Автор: Администратор


Код

def gcd(a, b):
    if a == 0:
        return b

    return gcd(b % a, a)
a,b=map(int,input().split())
res=gcd(a,b)
if(a==b):
    print(0)
else:
    a//=res
    b//=res
    temp=[2,3,5]
    ans=0

    while(a%2==0):
        a//=2
        ans+=1
    while(b%2==0):
        b//=2
        ans+=1
    while (a % 3 == 0):
        a //= 3
        ans += 1
    while (b % 3 == 0):
        b //= 3
        ans += 1
    while (a % 5 == 0):
        a //= 5
        ans += 1
    while (b % 5 == 0):
        b //= 5
        ans += 1
    if(a==1 and b==1):
        print(ans)
    else:
        print(-1)

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться