•题意
n 个people，编号1~n，按顺时针方向围城一圈；
初始，编号为1的people抱着一个球，他可以将球顺时针传给第 k 个people;
接到球的people将球传给他顺时针方向的第 k 个people，循环进行，直到球再一次落到 1 号 people 手中结束；
定义一个开心值 ：所有接到球的 people 的编号和。
求所有的开心值，并按升序排列。
•题解
弱弱的我只能通过打表找规律%%%%%%%那些一眼看出规律的大神们
===========
i=1 1 =========== i=2 1 3 =========== i=3 1 6 =========== i=4 1 4 10 =========== i=5 1 15 =========== i=6 1 5 9 21 =========== i=7 1 28 =========== i=8 1 6 16 36 =========== i=9 1 12 45 =========== i=10 1 7 25 55 =========== i=11 1 66 =========== i=12 1 8 15 22 36 78刚开始，发现，有些数的所有开心值只有两个，然后，把这些只有两个开心值得数列了一下，发现，全是素数。
不知为啥，求了一下每个数的因子个数，发现没，开心值的个数与他们的因子个数有关!!!!!!!
然后，在草纸上列出了前12项的答案，找了一下规律，哇，最后10分钟，找到了一个前10个通用的规律。
最后结束时刻提交,emmmmm，wa
然后，睡觉，哈哈哈
今天，把昨天的错误数据看了一下，重新找了一下规律
emmmm,找到了
以15为例
15的因子为1,3,5,15
开心值为1,18,35,120
1=1;
18=1+6+11; //d=5,tot=3
35=1+4+7+10+13; //d=3,tot=5
120=1+2+3+4+5+6+7+8+9+10+11+12+13+14+15; //d=1,tot=15
发现没，开心值就是以15的因子为公差的前 tot 项和
•Code
View Code1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define ll __int64 8 #define mem(a,b) memset(a,b,sizeof(a)) 9 const int maxn=1e6+10;10 11 ll n;12 ll a[maxn];13 ll res[maxn];14 15 int factor()//求出n的所有因子16 {17 int x=sqrt(n);18 a[1]=1;19 int index=1;20 for(int i=2;i <= x;++i)21 {22 if(n%i == 0)23 {24 a[++index]=i;25 if(n/i != i)26 a[++index]=n/i;27 }28 }29 a[++index]=n;30 return index;31 }32 int main()33 {34 scanf("%d",&n);35 int t=factor();36 sort(a+1,a+t+1);37 for(int i=1;i <= t;++i)38 {39 ll d=a[i],tot=n/d;40 ll a1=1,an=a1+(tot-1)*d;41 res[i]=tot*(a1+an)/2;42 }43 for(int i=t;i >= 1;--i)44 printf("%I64d ",res[i]);45 }
•打表找规律代码
View Code1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 #define ll __int64 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 const ll MOD=998244353; 9 const int maxn=1e6+10;10 11 int n;12 int a[maxn];13 14 int main()15 {16 for(int i=1;i <= 15;++i)17 {18 i=15;19 int tot=0;20 for(int k=1;k <= i;++k)21 {22 int res=1;23 int index=1+k;24 printf("****\nk=%d\n",k);25 printf("1");26 while(index != 1)27 {28 if(index > i)29 index %= i;30 if(index == 1)31 break;32 res += index;33 printf("+%d",index);34 index += k;35 }36 printf("=%d\n",res);37 a[tot++]=res;38 }39 40 sort(a,a+tot);41 int t=unique(a,a+tot)-a;42 printf("\n===========\ni=%d\n",i);43 for(int j=0;j < t;++j)44 printf("%d ",a[j]);45 break;46 }47 }48 //1 27 105 235 625 1275
•分割线2019.6.14
•感悟
因打表找规律而AC的题，不能当作正解，赛后补题，要花时间思考正解；
•想法
假设编号为①的传给他的下 k 个人，最终一定会回到①处；
假设传了 x 次回到①处，也就是 1+x*k = 1+y*n，即 x*k = y*n;
我们来分析一下这个等式可以推出什么神奇的东西：
为什么要最小的 x 呢？
因为只要传球期间来到①处就停止，所以需要的是最小的 x；
传球的序列为 1,1+k,1+2k,.....,1+xk（(1+ik)%(n+1) 为其实际编号，其中只有 (1+xk)%(n+1) = 0）
如果 GCD(k,n) = k，那么一轮便可以来到①处；
如果 GCD(k,n) ≠ k，那么需要多轮才能来到①处；
那么下面来讨论 GCD(k,n) ≠ k 的情况；
1)假设GCD(k,n) = 1;
那么，由上面推的公式可得 x = n，而这与 k = 1 时传球的次数相同，那传球的编号一样吗？
易得除了①以外，其余接到球的编号只出现一次；
假设某编号在传球期间两次接到球，并且在这期间球并没有回到①处，那么，这次传球就永远回不到①处了；
但是传 x 次球肯定能回到①处，所以假设不成立；
所以接到球的编号各不相同；
所以当GCD(k,n) = 1时，与 k = 1 时的情况重复；
2)假设GCD(k,n) = f;
这与当 k = f 时的情况重复；
x = n / f 与 k = f 时的传球次数相同，而对于第 i 次传球，接到球的编号为
而这与 k=f 时接到球的编号一样，又因为没有重复的，GCD(k,n) = f 的这 x 次传球与 k = f 重复；
综上，接到球的不同编号序列只与 n 的因子有关系；
