題意：給一個(gè)素?cái)?shù)n刻坊，求這樣的字符串枷恕，長(zhǎng)度為n-1,在尾部添加一個(gè)字符x，然后執(zhí)行n-1次這樣的操作：每k(1到n-1)個(gè)字符中提取一個(gè)字符谭胚，構(gòu)成長(zhǎng)度為n-1的新字符串。這樣未玻，就形成了n-1行的長(zhǎng)度為n-1的字符串灾而。其中的字符串要么是原來(lái)的字符串，要么是補(bǔ)字符串扳剿，也就是說(shuō)旁趟，結(jié)構(gòu)中只有兩種字符串，字符不能全部相同庇绽。(字符只包含0和1)
作者：kgduu
來(lái)源：CSDN
原文：https://blog.csdn.net/xiexingshishu/article/details/45771203
版權(quán)聲明：本文為博主原創(chuàng)文章，轉(zhuǎn)載請(qǐng)附上博文鏈接！
思路：
第一部分：列式子
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]
第二部分：結(jié)合兩種情況做差
①：1-2每一個(gè)都對(duì)應(yīng)相同
②：1-2每一個(gè)都對(duì)應(yīng)相反
由①得到：(一)
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]
...
第三部分：得到結(jié)論
觀察得到：a[iI%n]都會(huì)相同健霹，其他項(xiàng)都相同
又因?yàn)椋好恳晃徊荒芏枷嗤€要滿足整個(gè)01序列的字典序最小
再加上辟狈，a[11%n]是第一項(xiàng)肠缔，
所以，只要讓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;
}
