Gym 100199 A 解题报告
题目地址:
http://codeforces.com/gym/100199/attachments/download/1686/20022003-winter-petrozavodsk-camp-andrew-stankevich-contest-1-en.pdf
题目大意:
有n个人在传球
每个人会把球丢给她左边第k个人,因为k>n/2就没有意义了所以1<=k<=n/2
求最大的k,满足从1号开始n次,每个人都能拿到球并且回到1号
这是个数学题
如果n是奇数,那么答案是n/2
证明如下:
这是显然的,为什么要证明?
我们可以把问题等价于求最大的k使得gcd(n,k)=1
什么这个也要证?
实际上这个的证明比较神奇
我们来证明gcd(n,k)=1 --> k是合法解
假设存在a,b,使得ak%n=bk%n,a!=b(mod n)
那么ak=bk(mod n),gcd(n,k)=1 ==> a=b(mod n)
矛盾,X(PS:上述有的=实际上是三横)
我们来证明k是合法解 --> gcd(n,k)=1
假设k是合法解,gcd(n,k)!=1
那么存在t=n/gcd(n,k)
t<n,走过t次以后在0号位置,而n次以后也在0号位置
冲突,X
那么下面就要证明gcd(n/2,n)=1了
gcd(n/2*2,n)=gcd(n-1,n)=1
所以gcd(n/2,n)=1
如果n是偶数呢?
如果n/2是偶数,答案是n/2-1
如果n/2是奇数,答案是n/2-2 (n=2除外,此时答案是1,不过数据保证n>=3)
首先,n=2^a0*p1^a1*p2^a2...
然后我们不管和2的gcd,只看和p1^a1...pn^an的gcd
因为除了2以外,p>=3,所以
gcd(n/2-1,n/2)=1
gcd(n/2-2,n/2)=1(n/2是奇数)
在n/2是偶数的时候,gcd(n/2-1,n/2)=1,n/2-1是奇数,所以gcd(n/2-1,n)=1
在n/2是奇数的时候,gcd(n/2-2,n/2)=1,n/2-2是奇数,所以gcd(n/2-1,n)=1
没了
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include<set>#include<map>#include<list>#include<queue>#include<stack>#include<string>#include<time.h>#include<math.h>#include<memory>#include<vector>#include<bitset>#include<fstream>#include<stdio.h>#include<utility>#include<sstream>#include<string.h>#include<iostream>#include<stdlib.h>#include<algorithm>using namespace std;char a[4005];int b[4005];int c[4005];int main(){ freopen("china.in","r",stdin); freopen("china.out","w",stdout); scanf("%s",a); int i; int n=strlen(a); for (i=0;i<n;i++) { b[i]=a[i]-'0'; } int sum=0; for (i=0;i<n;i++) { sum*=10; sum+=b[i]; c[i]=sum/2; sum%=2; } if (sum==1) { for (i=0;i<n-1;i++) { if (c[i]!=0) break; } for (;i<n;i++) { printf("%d",c[i]); } puts(""); return 0; } if (c[n-1]%2==0) { c[n-1]--; } else { c[n-1]-=2; } int t=n-1; for (;t>=0;) { if (c[t]<0) { c[t]+=10; c[t-1]--; t--; } else { break; } } for (i=0;i<n-1;i++) { if (c[i]!=0) break; } for (;i<n;i++) { printf("%d",c[i]); } puts(""); return 0;} |
评论 (0)