第一题 鸽巢定理
1 #include <iostream>
2 using namespace std;
3 const int N=100000+5;
4 int a[N],q[N];
5 int main()
6 {
7 int T,n,m;
8 int ans=0;
9 int q;
10 cin>>T;
11 while(T--)
12 {
13 cin>>n>>m;
14 for(int i=0;i<n;i++)
15 {
16 cin>>a[i];
17 }
18 for (int j=0;j<n;j++)
19 {
20 ans+=a[j];
21 q[j]=ans%m;
22 }
23 q=ans%m;
24 for(int t=0;t<n;t++)
25 {
26 if
27 }
28 if (q==0) cout<<"YES"<<endl;
29 else cout<<"no"<<endl;
30
31 }
32 } 我的代码 卒于第二个判断条件
100000，又用两个for显然超时
正确代码，结构好一万倍，但思路还是那个：
1 #include <iostream>
2 using namespace std;
3 const int N=100000+5;
4 bool a[N];
5 int sum[N];
6
7 int main ()
8 {
9 int T;
10 cin>>T;
11 while (T--)
12 {
13 int n,m;
14 cin>>n>>m;
15 for(int j=0;j<N;j++)
16 {
17 a[j]=0;
18 sum[j]=0;
19 }
20 int flag=0;a[0]=1;
21 for (int i=1;i<=n;i++)
22 {
23 int u;
24 cin>>u;
25 sum[i]=(sum[i-1]+u)%m;
26 if(a[sum[i]]) flag=1;
27 else a[sum[i]] = 1;
28 }
29 if(flag==1) cout<<"YES"<<endl;
30 else cout<<"NO"<<endl;
31 }
32 } 给你一个n个数的数列，一定有连续的m（m<=n）个数是n的倍数，可以简单证明下：
假设有一n个数的序列，把他们的前缀和存到S[i]数组中，代表从第1个到第i个相加的和，
把他们全对n取余，那范围肯定只有0~n-1这n个数，特判0，肯定yes，
那只剩下1~n-1了，如果没有0那n个数，不可能只有n-1种情况，所以必定有重复的，不妨假设S[i]%n == S[j]%n !=0 (i < j) 此时用(S[j]-S[i])%n肯定为0，也就是说i到j为连续的序列是n的倍数
根据上面的证明，最后我们只要求一个Sn（1~n之和）对m取余，看是否有=0的情况，或者有两个相等的情况就yes，否则no。
第四题
1 #include<cstdio>
2 #include<algorithm>
3 #include<iostream>
4 using namespace std;
5 typedef long long LL;
6 typedef pair<LL, LL> PLL;
7 const int N=100000+5;
8 LL a[N],b[N],m[N];
9 //模板大法好。。。
10 LL gcd(LL a,LL b)
11 {
12 return b?gcd(b,a%b):a;
13 }
14
15 void ex_gcd (LL a,LL b,LL &x,LL &y,LL &d)
16 {
17 if(!b)
18 {
19 d=a;
20 x=1;
21 y=0;
22 }
23 else
24 {
25 ex_gcd(b,a%b,y,x,d);
26 y -= x*(a/b);
27 }
28 }
29
30 LL inv(LL t ,LL p)
31 {
32 LL d,x,y;
33 ex_gcd(t,p,x,y,d);
34 return d==1?(x%p+p)%p:-1;
35 }
36
37 PLL linear(LL A[], LL B[], LL M[], int n)
38 {//求解A[i]x = B[i] (mod M[i]),总共n个线性方程组
39 LL x = 0, m = 1;
40 for(int i = 0; i < n; i ++)
41 {
42 LL a = A[i] * m, b = B[i] - A[i]*x, d = gcd(M[i], a);
43 if(b % d != 0) return PLL(0, -1);//答案不存在，返回-1
44 LL t = b/d * inv(a/d, M[i]/d)%(M[i]/d);
45 x = x + m*t;
46 m *= M[i]/d;
47 }
48 x = (x % m + m ) % m;
49 return PLL(x, m);//返回的x就是答案，m是最后的lcm值
50 }
51
52 int main()
53 {
54 int k;
55 while (cin>>k&&k)
56 {
57 for(int i=0;i<k;i++)
58 {
59 a[i]=1;
60 cin>>m[i]>>b[i];
61 }
62 PLL ans =linear(a,b,m,k);
63 if(ans.second==-1) cout<<"-1"<<endl;
64 else cout<<ans.first<<endl;
65 }
66 return 0;
67 } 欧几里得
拓展欧几里得
模板
在这里学到的一点是 一个函数往回返回两个值要怎么返回 typedef pair <LL, LL> PLL
调用就是 PLL ans ;;;; ans.firsst /ans.second....
转载于:https://www.cnblogs.com/jzzb/p/9366506.html