題干：

One industrial factory is reforming working plan. The director suggested to set a mythical detail production norm. If at the beginning of the day there were?x?details in the factory storage, then by the end of the day the factory has to produce??(remainder after dividing?x?by?m) more details. Unfortunately, no customer has ever bought any mythical detail, so all the details produced stay on the factory.

The board of directors are worried that the production by the given plan may eventually stop (that means that there will be а moment when the current number of details on the factory is divisible by?m).

Given the number of details?a?on the first day and number?m?check if the production stops at some moment.

Input

The first line contains two integers?a?and?m?(1?≤?a,?m?≤?105).

Output

Print "Yes" (without quotes) if the production will eventually stop, otherwise print "No".

Examples

Input

1 5

Output

No

Input

3 6

Output

Yes

題目大意：

?給兩個數a和m，每天進行一次操作，a = (a+a%m)%m， 問a是否有可能等于0思路：

解題報告：

本來想直接看gcd、、、但是仔細讀題發現不行，因為他這個沒大有規律啊、、、所以沒有類似的結論可以用，

因為a和m小于10^5，而且a每次都要取余，所以a每天操作之后的變成的值肯定小于m，即小于10^5，開個vis數組，記錄下a曾經取過什么數，每次操作后判斷如果a出現過，那就是進入循環了輸出No，如果a==0就符合要求輸出Yes。

根據抽屜原理，最多進行m+1天一定會有重復出現的余數，時間復雜度O(m)。

當然這題還有個O(logm) 的做法：

我們推算兩步：(a + (a mod m)) mod m = ((a mod m) + (a mod m)) mod m = (2*a) mod m。也就是說接下來的所有答案都是2的冪次，也就是說?如果存在K?≥?0 ，使得，那么輸出Yes，否則輸出No。題目范圍1e5，也就是說我們只需要推算大概20步，就可以break了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n,x,y,a[MAX],ans; const ll INF = 0x3f3f3f3f3f; int main() {ll a,m;int flag = 0;scanf("%lld%lld",&a,&m);for(int i = 1; i<=100000; i++) {if(a%m == 0) flag = 1;a = (a+a)%m;}if(flag) puts("Yes");else puts("No");return 0; }

?

總結

以上是生活随笔為你收集整理的【CodeForces - 485A】Factory （水题，抽屉原理，tricks）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。