[TJOI2009]猜数字
发布时间:2020-12-14 04:35:33 所属栏目:大数据 来源:网络整理
导读:Description 现有两组数字,每组k个,第一组中的数字分别为:a1,a2,...,ak表示,第二组中的数字分别用b1,b2,...,bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n,满足对于任意的i,n - ai能被bi整除。 Input 输入数据的第一行是一个整数k
Description Input Output Sample Input Sample Output (b_i|n-a_i),意味着(nequiv a_i(%b_i)),所以我们列个方程 /*program from Wolfycz*/ #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define inf 0x7f7f7f7f using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; inline char gc(){ static char buf[1000000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++; } template<typename T>inline T frd(T x){ int f=1; char ch=gc(); for (;ch<'0'||ch>'9';ch=gc()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=gc()) x=(x<<1)+(x<<3)+ch-'0'; return x*f; } template<typename T>inline T read(T x){ int f=1;char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1; for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0'; return x*f; } inline void print(int x){ if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0'); } namespace Math{ ll mlt(ll _a,ll _b,ll _p){ ll _c=(ld)_a*_b/_p; ll _Ans=_a*_b-_c*_p; if (_Ans<0) _Ans+=_p; return _Ans; } ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} void exgcd(ll a,ll b,ll &x,ll &y){ if (!b){x=1,y=0;return;} exgcd(b,a%b,x,y); ll t=x; x=y,y=t-a/b*y; } ll Ex_GCD(ll a,ll c){ ll d=gcd(a,b),y; if (c%d) return -1; a/=d,b/=d,c/=d; exgcd(a,b,y); x=(mlt(x,c,b)+b)%b; return x; } } int A[15],m[15]; int main(){ int n=read(0); ll SM=1,Ans=0; for (int i=1;i<=n;i++) A[i]=read(0); for (int i=1;i<=n;i++) SM*=(m[i]=read(0)); for (int i=1;i<=n;i++){ ll M=SM/m[i],res=Math::mlt(A[i],Math::Ex_GCD(M,m[i],1),SM); Ans=(Ans+Math::mlt(res,M,SM))%SM; } printf("%lldn",Ans); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- [lua]使用lua解析器直接运行lua代码
- VB 判断 WebBrowser是否已经加载网页完毕
- delphi – Word自动化仅适用于管理员,或者在创建word.appli
- java – Spring Boot YML和StandAlone Tomcat 8 Server
- bigdata – 将Google Cloud Storage存储桶移至另一个项目
- VB.Net程序设计:多列ComBoBox控件中初始化网格的代码段
- java – 如何使用Spring Roo和JPA提供我自己的@id字段
- perl closure object闭包和对象
- perl – 安全隔间中的“无警告”
- 如何为简单的Perl词典应用程序正确格式化纯文本数据?