首页 > 代码库 > Codeforces Round #276 (Div. 2)A. Factory（数论）
Codeforces Round #276 (Div. 2)A. Factory（数论）
这道题可以暴力的一直按要求的方法去做，做1000000次还不能整除m就认为永远不能整除m了（m不超过100000，循环1000000次比较安全了已经）。这种方法可以AC。
下面深入的分析一下到底循环多少次就可以确定结果：首先有这样一个规律：(a+b)%c=(a%c+b%c)%c,那么这样其实这道题每次就是2*a。官方题解说的好：
Production will stops iff exists integer K ≥ 0 such a·2K is divisible by m. From this fact follows that K maximum will be about O(log2(m)). So if we modeling some, for example, 20 days and production does not stop, then it will never stop and answer is "No". Otherwise answer is "Yes".
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=1000+5;int a,m;int main(){ //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d",&a,&m);int w=0; for(int i=0;i<20;i++) { if(a%m==0){w=1;puts("Yes");break;} a%=m; a+=a; } if(w==0)puts("No"); //fclose(stdin); //fclose(stdout); return 0;}
或者不这么想也行，就去找周期性的规律也可以，但是注意周期不一定从第一个数开始，其实只要后面的a%m有在前面出现过了，那就不用再算下去了，肯定后面都一样。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=1000+5;int a,m;set<int>s;int main(){ cin>>a>>m; while(a%m!=0){ if(s.find(a%m)!=s.end()){cout<<"No"<<endl; return 0;} s.insert(a%m); a += (a%m); } cout<<"Yes"<<endl; return 0;}
Codeforces Round #276 (Div. 2)A. Factory（数论）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。