2017 ACM-ICPC 亚洲区（西安赛区）网络赛 Sum

构造题

先上代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
string x;
string ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> x;
        int l = x.length();
        ans = "1";
        string seg(l-1,'0');
        seg += '1';
        for (int i = 1; i < 233; ++i)
            ans += seg;
        cout<<ans<<endl;
    }
    return 0;
}

解释

update 2019年4月23日12点41分
其实下面说什么质数的都是不必要的，普通的整数也是可以的。
下面是原内容

Z p Z_p Zp​(即 &lt; Z p , + &gt; &lt;Z_p,+&gt; <Zp​,+>)是个循环群，且除了 0 0 0以外的 p − 1 p-1 p−1个元素都是生成元，阶都是 p . p. p.
因此如果 p p p个a相加(这里指 Z p Z_p Zp​群中的相加)，则一定是 0. 0. 0.
而这个里的 233 233 233就是个质数，并且是模数
题目是要 k x kx kx的每一位相加模 233 233 233为0
我的代码就是构造了 k x kx kx为 x x x . . . x xxx...x xxx...x(共233,这里不是指相乘)的数。
举个例子：
我们把233换成5来说明：
x = 4589 x=4589 x=4589
我构造的数是
45894589458945894589 45894589458945894589 45894589458945894589
S ( 45894589458945894589 ) = 5 × S ( 4589 ) S(45894589458945894589)=5 \times S(4589) S(45894589458945894589)=5×S(4589)
如果换成233个4589，则
S ( 45894589...4589 ) = 233 × S ( 4589 ) S(45894589...4589)=233\times S(4589) S(45894589...4589)=233×S(4589)
而对于这个数kx的k也是很明显的
x最多7位
k最多就是 233 ∗ 7 − 2 &lt; 2000 233*7-2&lt;2000 233∗7−2<2000

update 2019年4月23日12点42分
下面是更新后的内容

补充

实际上，从后面的构造方法来看，就算233换成一个非素数也是可以的。
因为 Z n Z_n Zn​就是个循环群，并且每个元素的 阶 阶 阶都是 n n n的因子。只要n个运算，则肯定是回到 0 0 0了。