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