HDU 1573 X问题
2018-06-17 21:16:34来源:未知 阅读 ()
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7221 Accepted Submission(s):
2551
还是裸的扩展CRT
注意边界情况
题目中有X=0的坑数据,注意特判
#include<iostream> #include<cstdio> #include<cstring> #define LL long long using namespace std; const int MAXN=1e6+10; int N,K,C[MAXN],M[MAXN],x,y; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int exgcd(int a,int b,int &x,int &y) { if(b==0){x=1,y=0;return a;} int r=exgcd(b,a%b,x,y),tmp; tmp=x;x=y;y=tmp-(a/b)*y; return r; } int inv(int a,int b) { int r=exgcd(a,b,x,y); while(x<0) x+=b; return x; } int main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif int T; scanf("%d",&T); while(T--) { memset(M,0,sizeof(M)); memset(C,0,sizeof(C)); scanf("%d%d",&N,&K); for(int i=1;i<=K;i++) scanf("%d",&M[i]); for(int i=1;i<=K;i++) scanf("%d",&C[i]),C[i]%=M[i]; bool flag=1; for(int i=2;i<=K;i++) { int M1=M[i-1],M2=M[i],C2=C[i],C1=C[i-1],T=gcd(M1,M2); if((C2-C1)%T!=0) {flag=0;break;} M[i]=(M1*M2)/T; C[i]= ( inv( M1/T , M2/T ) * (C2-C1)/T ) % (M2/T) * M1 + C1; C[i]=(C[i]%M[i]+M[i])%M[i]; } if(flag==0) printf("0\n"); else { if(N<C[K]) printf("0\n"); else { int ans=(N-C[K])/M[K]+1; //if(C[K]) ans++; printf("%d\n",ans); } } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:C++11新特性学习
- WDK驱动调试问题点滴 2020-04-21
- 螺旋矩阵问题 2020-04-18
- 用C++实现:完美的代价 2020-04-15
- 用C++实现:FJ的字符串打印 2020-04-04
- HDU-2955-Robberies(0-1背包) 2020-03-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash