2010年1月28日星期四.sgu137
sgu137:数学推导,模的艺术
输入两个数n，m
对于一个序列
A[0...n-1] = 0.....1
B[0...n-1] = 1.....0
如果(B)能由(A)左转或者右转形成，那么也就是说，
存在一个元素k，对于每个元素A[i]都有，A[(i+k)%n] = B[i];
由B[0] == 1可以知道，一定有A[k] == 1;
又由于中间的省略号部分元素是相同的。
所以一定有B[k] == 1,继续推导，也一定有A[(k+k)%n] == 1,当最后推导到A[n-1] == 1时停止。
也就是最后要使 (m * k + 1) % n == 0
然后我们要做的也就是找到这个k即可。
1 const int N = 1024;
2 int n,m,off,a[N];
3 int main()
4 {
5 int i,k;
6 scanf("%d%d",&n,&m);
7 off = m / n;
8 m %= n;
9 for (k = 0;(m * k + 1) % n;k++);
10 for (i = k;m--;(i+= k) %= n) { a[i] = 1; }
11 for (i = 0;i < n;i++) {
12 printf("%d ",a[i] + off);
13 }
14 printf("\n");
15 return 0;
16 }
17