sgu 137. Funny Strings 线性同余,数论,构造 难度:3

137. Funny Strings

time limit per test: 0.25 sec. 
memory limit per test: 4096 KB

Let's consider a string of non-negative integers, containing N elements. Suppose these elements are S S .. S, in the order in which they are placed inside the string. Such a string is called 'funny' if the string S+1 S S .. S S-1 can be obtained by rotating the first string (to the left or to the right) several times. For instance, the strings 2 2 2 3 and 1 2 1 2 2 are funny, but the string 1 2 1 2is not. Your task is to find a funny string having N elements, for which the sum of its elements (S+S+..+S) is equal to K.

Input

The input contains two integers: N (2<=N<=1000) and K (1<=K<=30000). Moreover, GCD(N,K)=1 (it can be proven that this is a necessary condition for a string to be funny).

Output

You should output one line containing the elements of the funny string found. These integers should be separated by blanks.

Hint

GCD(A,B) = the greatest common divisor of A and B. 
The 'funny' strings are also named Euclid strings in several papers.

Sample Input

9 16

Sample Output

1 2 2 2 1 2 2 2 2

首先k/n的部分可以平均分配,比如9,16,每个元素都先+1,接下来就只有0,1需要分配了

接着,因为gcd(n,k)==1,所以必然存在一个数gap在[1,n-1]内,使[0,n-1]所有整数temp都被[gap*temp%n]遍历(为了防止有重合),且恰好使k*gap%n==n-1的
然后根据[(gap*i)%n]遍历到的第i项(1<=i<=k)都赋1,其它的都赋0就行了
也就是向右旋转gap次,恰好都落在下一个遍历的位置上,第0个位置赋1,第k个位置赋0,其他位置都不变,这样恰好翻转
从题目的方面,所有的位置必然处在gap*temp循环之内否则会有a[0]==a[n-1]出现不满足题意

#include<cstdio>

using namespace std;

int bit[35000];

int main(){

    int n,k;

    scanf("%d%d",&n,&k);

    int t=k/n;

    k%=n;

    int gap=1;

    for(int i=1;i<n;i++){

        if((long long)i*k%n==n-1){

            gap=i;

            break;

        }

    }

    for(int i=1;i<=k;i++){

        bit[(long long )(gap*i)%n]=1;

    }

    for(int i=0;i<n;i++){

        printf("%d%c",t+bit[i],i==n-1?'\n':' ');

    }

    return 0;

}