1153

题意：给一个素数n，求这样的字符串，长度为n-1,在尾部添加一个字符x，然后执行n-1次这样的操作：每k(1到n-1)个字符中提取一个字符，构成长度为n-1的新字符串。这样，就形成了n-1行的长度为n-1的字符串。其中的字符串要么是原来的字符串，要么是补字符串，也就是说，结构中只有两种字符串，字符不能全部相同。(字符只包含0和1)

作者：kgduu
来源：CSDN
原文：https://blog.csdn.net/xiexingshishu/article/details/45771203
版权声明：本文为博主原创文章，转载请附上博文链接！

思路：
第一部分：列式子
1.a[1%n] a[2%n]......a[n-1%n]
2.a[2%n] a[4%n]......a[2(n-1)%n]
3.a[3%n] a[6%n]........
4...
..
..
n-1： a[(n-1)%n] a[2(n-1)%n]......a[(n-1)*(n-1)%n]

第二部分：结合两种情况做差
①：1-2每一个都对应相同
②：1-2每一个都对应相反
由①得到：(一)
a[1%n]=a[2%n]
a[2%n]=a[4%n]
...
...
a[(n-1)%N]=a[2(n-1)%n]
由②得到：（二）
a[1%n]!=a[2%n]
a[2%n]!=a[4%n]
...
...
a[(n-1)%n]!=a[(n-1)%n]
将一、二合并：
（三）
a[1%n]=a[4%n]
a[2%n]=a[6%n]
...
第三部分：得到结论
观察得到：a[iI%n]都会相同，其他项都相同
又因为：每一位不能都相同，还要满足整个01序列的字典序最小
再加上，a[11%n]是第一项，
所以，只要让a[ii%n]=0，其他=1，即可

#include<bits/stdc++.h>
#define ll long long
#define maxsize 1000000
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int p,a[maxsize];
int main()
{
    while(cin>>p&&p)
    {
        if(p<3)
        {
            printf("Impossible\n");
            continue;
        }
        mem(a,0);
        for(ll i=1;i<p;++i)
        {
            a[(i*i)%p]=1;
        }
        for(ll i=1;i<=p-1;++i)
            printf("%d",!a[i]);
        cout<<endl;
    }
    return 0;
}