十二省联考2019 骗分过样例

---

1_998244353

出题人的良心送肉点，前三个输入是1,2,3，输出是1,19,361，显然是19的n次方，模数就是给的998244353

第三个点n有40位，看似要高精度其实按照读入优化方法读进来以后对\(\varphi(998244353)=998244352\)取膜再快速幂就行了

屎鸡还说要python真的呆

1?

998244353没了应该是要猜模数，那我就先读进所有答案取个最大值猜一下

1145099

那我一直往后试模数吧。。（py3自带快速幂还是很牛逼的）

import sys,os,randomfin=open("4.in")fans=open("4.ans")fin.readline()fin.readline()n=int(fin.readline())inputs=[]outputs=[]for i in range(n):    inputs.append(int(fin.readline()))    outputs.append(int(fans.readline()))Mod=1145099while 1:    Mod+=1    yes=1    for i in range(n):        if pow(19,inputs[i],Mod)!=outputs[i]:            yes=0            break    if yes:breakprint(Mod)

$ python3 4.py1145141

这模数牛逼

1?+

应该还是猜模数，同样方法求最大值，5211500658258874318

好像跑一小会跑不出来啊，想一下怎么做呢。。

然后就去膜题解了。。。

有这样两组数据，

264708066 1996649514996338529264708068 1589589654696467295

设

x=264708066 a=1996649514996338529

y=264708068 b=1589589654696467295

那么\(a\times 19^2\equiv b(\mod Mod)\)

\(Mod|(a\times 19^2-b)\)

那么上一个单位根反演

\(Mod\)必须是这个东西的约数而且\(>5211500658258874318\)。

先看看这个东西是\(719200885258981741674=2\times3\times23\times\)。。。。怎么回事我质因数分解写挂了？

剩下那个是\(5211600617818708273\)，好像只比答案最大值大一点点，就是这个

1wa_998244353

果然WA了啊，stm还有负数，提示好像给了自然溢可能就是说这个的

但是这里因为不知道怎么溢的，不能快速幂，就很鸡贼了

又膜题解去了。。。

stm用map找周期。。。佛了

这个周期贼小啊，从n=55245到n=100944

2p

开新档啦。。。

因为前面几个ans直接用gedit打开都没有问题，然后我打开了8.ans

我电脑就卡死了。。。

死了。。。

了。。。

（慌得直接打开9.ans）

这输出字符串？？完全看不懂啊，，，连长度都看不懂。。。

看了一眼最后一个串的长度，\(10^6\)

所以串长就是b-a+1了

看到b-a+1很容易想到r-l+1？

然后先看第一个

1 2 3 4 5 6 7 8 9 10

/ p p . p . p . . .

所以p应该就是质数的意思

所以这题就是给一段区间求这些数是不是质数

好像是miller_rabin裸题。。

2u

p是质数的意思，那么u是什么鬼。。。

打开输入文件有+，-和0，那么应该是莫比乌斯函数

然后膜题解去了

对每个数先计算\(10^6\)以内的质因数，那么去掉这些以后这个数只有四种可能：1、质数、完全平方数和两个不同质数之积。这个就很好判了

2g

g就是判原根。

根据以前的知识可以知道，对于质数\(p\)，对\(p-1\)进行唯一分解，\(p-1=\prod p_i^{e_i}\)，那么\(a\)是\(p\)的原根当且仅当对于每个\(i\)都有\(a^{\frac{p-1}{p_i}}\mod p\neq 1\)。

那么第一个点\(p=998244353\)，\(p-1=998244352=2^{x}\cdot 7\cdot 17\)，只需要暴力就行了。

第二个点\(p=13123111\)就很麻烦，发现\(p-1=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 19\cdot 23\)，但\(p\)不是很大，查询的范围是1-(p-1)，可以预处理，对于这些因子的倍数，筛掉它，它不是\(p\)的原根。剩下的都是。

第三个点要猜\(p\)，只给了\(p\in [10^9,2\cdot 10^9]\)。那么就一个一个猜啊。。。。当然我是不可能一个一个猜的，直接抄题解。。。。

LOJ格式化以后的正常瞎比打空格的代码

#include 
    
     #define il inline#define vd void#define st statictypedef long long ll;il ll gi() {    ll x;    scanf("%lld", &x);    return x;}std::string op;il ll mul(ll x, ll y, ll m) { return (x * y - m * (ll)((long double)x * y / m + 0.5) + m) % m; }il int wa_mul(int a, int b, int m) { return a * b % m; }il ll pow(ll x, ll y, ll m) {    ll ret = 1;    while (y) {        if (y & 1)            ret = mul(x, ret, m);        x = mul(x, x, m);        y >>= 1;    }    return ret;}il bool miller_rabin(ll x, int op = 0) {    if (x < 2)        return 0;    if (x == 2)        return 1;    if (!(x & 1))        return 0;    ll t = 0, _x = x - 1;    st int c[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 24251 };    while (!(_x & 1)) _x >>= 1, ++t;    for (int i = op; i < 10; ++i) {        if (x == c[i])            return 1;        ll p = pow(c[i], _x, x);        if (p == 1 || p == x - 1)            continue;        int T = t;        while (T--) {            p = mul(p, p, x);            if (p == x - 1)                break;        }        if (T == -1)            return 0;    }    return 1;}int main() {    std::cin >> op;    if (op[0] == '1' && op[1] != 'w') {        ll m;        if (op[1] == '_')            m = 998244353;        else if (op.size() == 2)            m = 1145141;        else            m = 5211600617818708273ll;        int n = gi();        st char s[50];        while (n--) {            scanf("%s", s + 1);            int l = strlen(s + 1);            ll p = 0;            for (int i = 1; i <= l; ++i) p = (p * 10 + s[i] - '0') % (m - 1);            printf("%lld\n", pow(19, p, m));        }    } else if (op == "1wa_998244353") {        st std::map
     
       mp;        st std::vector
      
        vec;        int begin, end;        vec.push_back(1);        for (int i = 1, x = 19;; ++i, x = x * 19 % 998244353) {            if (mp.find(x) == mp.end())                mp[x] = i, vec.push_back(x);            else {                begin = mp[x], end = i;                break;            }        }        int n = gi();        while (n--) {            ll x = gi();            if (x < begin)                printf("%d\n", vec[x]);            else                printf("%d\n", vec[begin + (x - begin) % (end - begin)]);        }    } else if (op == "2p") {        int n = gi();        while (n--) {            ll l = gi(), r = gi();            for (ll i = l; i <= r; ++i) putchar(".p"[miller_rabin(i)]);            puts("");        }    } else if (op == "2u") {        st ll mu[1000010], duliu[1000010], primes[78500], pr;        st bool yes[1000010];        for (int i = 2; i < 1000001; ++i) {            if (!yes[i])                primes[++pr] = i;            for (int j = 1; j <= pr && primes[j] * i < 1000001; ++j) {                yes[i * primes[j]] = 1;                if (i % primes[j] == 0)                    break;            }        }        int n = gi();        while (n--) {            ll l = gi(), r = gi();            for (int j = 0; j <= r - l; ++j) mu[j] = 1, duliu[j] = 1;            for (int j = 1; j <= pr; ++j)                for (ll k = l / primes[j]; k <= r / primes[j]; ++k) {                    if (k * primes[j] - l < 0)                        continue;                    if (k % primes[j])                        mu[k * primes[j] - l] *= -1, duliu[k * primes[j] - l] *= primes[j];                    else                        mu[k * primes[j] - l] = 0;                }            for (ll j = l; j <= r; ++j) {                if (mu[j - l]) {                    ll x = j / duliu[j - l];                    if (x == 1)                        ;                    else if (((ll)sqrt(x)) * ((ll)sqrt(x)) == x)                        mu[j - l] = 0;                    else if (miller_rabin(x, 9))                        mu[j - l] *= -1;                }                if (mu[j - l] == 0)                    putchar('0');                else                    putchar(mu[j - l] == 1 ? '+' : '-');            }            puts("");        }    } else {        int n = gi(), m;        while (n--) {            int l = gi(), r = gi();            if (l == 233333333)                m = 1515343657;            else                m = gi();            if (m == 998244353)                for (int i = l; i <= r; ++i)                    putchar("g."[pow(i, m / 2, m) == 1 || pow(i, m / 7, m) == 1 || pow(i, m / 17, m) == 1]);            else if (m == 13123111) {                st int f[13123122];                st bool yes[13123122];                for (int i = 1, g = 6; i < m; ++i, g = g * 6 % m) f[g] = i;                int p[] = { 2, 3, 5, 7, 11, 13, 19, 23 };                for (int o = 0; o < 8; ++o)                    for (int i = p[o]; i <= m; i += p[o]) yes[i] = 1;                for (int i = l; i <= r; ++i) putchar("g."[yes[f[i]]]);            } else                for (int i = l; i <= r; ++i)                    putchar("g."[pow(i, m / 2, m) == 1 || pow(i, m / 3, m) == 1 || pow(i, m / 4003, m) == 1 ||                                 pow(i, m / 15773, m) == 1]);            puts("");        }    }    return 0;}
      
     
    

压行（压成一行）之后的2.7K代码

#include
    
     #define il inline#define vd void#define st statictypedef long long ll;il ll gi(){ll x;scanf("%lld",&x);return x;}std::string op;il ll mul(ll x,ll y,ll m){return (x*y-m*(ll)((long double)x*y/m+0.5)+m)%m;}il int wa_mul(int a,int b,int m){return a*b%m;}il ll pow(ll x,ll y,ll m){ll ret=1;while(y){if(y&1)ret=mul(x,ret,m);x=mul(x,x,m);y>>=1;}return ret;}il bool miller_rabin(ll x,int op=0){if(x<2)return 0;if(x==2)return 1;if(!(x&1))return 0;ll t=0,_x=x-1;st int c[]={2,3,5,7,11,13,17,19,23,24251};while(!(_x&1))_x>>=1,++t;for(int i=op;i<10;++i){if(x==c[i])return 1;ll p=pow(c[i],_x,x);if(p==1||p==x-1)continue;int T=t;while(T--){p=mul(p,p,x);if(p==x-1)break;}if(T==-1)return 0;}return 1;}int main(){std::cin>>op;if(op[0]=='1'&&op[1]!='w'){ll m;if(op[1]=='_')m=998244353;else if(op.size()==2)m=1145141;else m=5211600617818708273ll;int n=gi();st char s[50];while(n--){scanf("%s",s+1);int l=strlen(s+1);ll p=0;for(int i=1;i<=l;++i)p=(p*10+s[i]-'0')%(m-1);printf("%lld\n",pow(19,p,m));}}else if(op=="1wa_998244353"){st std::map
     
      mp;st std::vector
      
       vec;int begin,end;vec.push_back(1);for(int i=1,x=19;;++i,x=x*19%998244353){if(mp.find(x)==mp.end())mp[x]=i,vec.push_back(x);else {begin=mp[x],end=i;break;}}int n=gi();while(n--){ll x=gi();if(x