Krolia的计时难题
Time Limit: 1000 ms Memory Limit: 65535 kB
Description
时间是最难以捉摸的东西,光是测量它们就已经很难了。一般而言,测量时间用一个可重复等时长发生的事件来定义最小的时间可测单位。于是Krolia想到了一个测量时间的好方法。
Krolia有一盒火柴,如果把火柴的头去掉火柴就会变成一样长的木棍。Krolia知道一根(没有火柴头)木棍一端点燃后,整个燃烧会持续x时间。Krolia还可以从两端同时点燃木棍,这样燃烧会持续x/2时间。现在Krolia想用这堆火柴来计时,问什么样的时间可以被完全精确地计算出。
Input
第一行一个整数T(T<=1000),表示有T组测试数据,每组测试数据行三个整数a,b,x(1<=a,b,x<=10^9)表示要测量a/b,一根火柴的燃烧时长是x时间。
Output
一个字符串,"YES"或者"NO"表示能或者不能被精确计算。
Sample Input
4
1 1 1
1 2 1
1 4 1
1 5 1
Sample Output
YES
YES
YES
NO
Hint
从一端点燃一根木棍。从两端同时点燃一根木棍。从两端同时点燃一根木棍的同时,从一端点燃一根木棍。当第一根木棍燃烧殆尽的时候,把剩下的那根木棍的火熄灭。最后把剩下的木棍的两端同时点燃。
Source
KroliaFansClub
分析可知,a=b*x*k/2^m(k,m为正整数)
则有a'/b'*x'=k; a'为将a中的约数2去除后的数,以此类推
#include<iostream> using namespace std; int main() { long long T,a,b,x; cin>>T; while(T--) { cin>>a>>b>>x; x=b*x; while(!(a%2)) a>>=1; while(!(x%2)) x>>=1; if(a%x) cout<<"NO"<<endl; else cout<<"YES"<<endl; } }