[十二省聯考2019]騙分過樣例

• 2019 年 11 月 1 日
• 筆記

傳送門

　　這道題是個毒瘤題，花費了博主(text{1day})獨立解決(16)個子任務。下面步入正題。

subtask 1-3:1_998244353

　　這個觀察數據不難得出要求(19^xbmod 998244353)，直接搞即可。注意到可能(x)非常大，根據費馬小定理(x^{P-1} equiv 1 pmod P)，我們需要讀入取模。

subtask 4:1?

　　觀察數據和提示告訴我們：仍然求(19^x)，只不過模數不知道。發現輸出文件的最大值在(10^6)左右，我們拿第一個輸入直接爆搜檢驗，最後能找出來(P=1145141)。

subtask 5:1?+

　　這個是前一個的加強版，發現模數在(5times 10^{18})左右，這個不好暴力了。怎麼辦呢？我把輸入的數排了個序，發現有兩組輸入的(x)之差為(2)，於是我找到這兩組對應的輸出，得到了：(19^{264708066}equiv 1996649514996338529 pmod P)和(19^{264708068}equiv 1589589654696467295 pmod P)。也就是說上面的式子乘上(19^2)再取模就能得到下面的數字，於是我們得到了：(1996649514996338529times 19^2 equiv 1589589654696467295 pmod P)。然後改寫這個式子：(1996649514996338529times 361-nP=1589589654696467295)，把常數移到右邊，發現在(long long)範圍內無法算出，我用(long double)算出了近似值。然後(P)一定是這個數的一個因子。發現(n)在(100)到(200)以內，我就暴力試除，考慮到精度又將除出來的模數以及(pm 1000)以內的用第一組輸入輸出判斷了一下，最後找到了模數(P=5211600617818708273)。

subtask 6-7:1wa_998244353

　　發現並不是求(19^x bmod 998244353)了，換成了用(int)一步一步直接乘再取模，忽視溢出等問題。代碼如下。

    x = (int)(x * 19) % 998244353;

　　第(6)個點直接順序求解即可。第(7)個點恐怕不太行，(x)太大了。我一開始想改寫快速冪來求解，發現行不通。正當我一籌莫展的時候，我讓第(6)個點多跑到(10^6)組，發現了循環節。就是從(x=55246)開始，每過(45699)個數循環一次。這讓我想起了(text{Pollard-Rho})算法的環和(rho)很像。當然與那個算法沒有關係，這裡直接用上述性質即可。

subtask 14-16:2g && 2g+

　　當時我在做完前面(6)個(text{subtask})後緊接着做的。前面兩個點，每次詢問給你三個數(l)，(r)，(P)，要求(l)到(r)在模(P)下的原根。對於第(14)個點，(P=998244353)時，(varphi(P)=P-1=998244352=2^{23}times 7times 17)，因為不同的質因子只有(3)個，所以可以直接試除判斷是否為原根。

　　對於第(15)個點，(P=13123111)，(varphi(P)=13123110=2×3×5×7×11×13×19×23)，而且判斷的數字多達(10^7)個，試除肯定會(text{T})，而我們可以利用其中一個原根把其他的原根遍歷出來。在這裡(g)取(6)，因為(g^t)遍歷所有(varphi(P))個與(P)互質的數，而當且僅當(t)與(varphi(P))互質的時候(g^t)也是原根。於是我們用(varphi(P))的質因子對(t)進行取模判斷。遍歷完後原根就找全了。

　　對於第(16)個點，最後一組詢問未知模數，根據數據給的原根我們反求模數。提示說在(10^9)到(2times 10^9)之間且是個質數，我們一個一個找，然後藉助已有的原根通過試除法判斷這個質數可不可行。(forall g)，如果(g^frac{P-1}{2}notequiv 1 pmod P)，則(P)很可能是我們要找的模數。我的電腦跑了大約(5min)找到了一個數(P=1515343657)，然後檢驗發現是正確的。用它搜原根與用(P=998244353)的方法一樣。於是就解決了。

subtask 8-10:2p

　　要求我們判斷(l)到(r)內每個數是不是質數。小範圍的可以用線性篩，範圍稍微大點的可能可以篩一部分數然後用這部分數來篩(l)到(r)，但我直接上了(text{Miller-Rabin})，這個算法可以在(log n)的時間內測試一個數是不是質數，正確率為(1-(frac{1}{4})^s)，(s)為測試次數。這題貌似選取兩三個數就可以了，這樣常數小全能過。

subtask 11-13:2u

　　這裡讓我們篩出(l)到(r)的莫比烏斯函數。

　　同上面一樣，我們可以小範圍地篩出來(mu)過掉前兩個點。當時我沒有這麼想，用了(text{Pollard-Rho})來暴力分解然後篩出前(10^6)個莫比烏斯函數，發現第二個點都過不掉。怎麼辦呢？最大的數為(10^{18})，我想到如果篩出(10^6)以內的質數然後用這些質數來篩這些數，剩下的數的素因子一定(geq 10^6)，所以剩下的數最多只能有兩個素因子，也就是以下三種情況：

　　一、剩下的數是質數，用(text{Miller-Rabin})判一下，這個時候會使(mu)乘上(-1)；

　　二、剩下的數是兩個不同的質數的乘積；負負得正，這個時候不會對(mu)產生貢獻；

　　三、剩下的數是一個質數的平方。這個時候(mu)為(0)。

　　然後用小於(10^6)的因子去篩這些數，並且維護(mu)，即可求解。

　　但要注意要去掉含有平方因子的數。最後這道題就解完了。

\ AC代碼  #include <bits/stdc++.h>    using namespace std;    #define ll long long  #define ull unsigned long long  #define rep(i, a, b) for (register int i = a, end = b; i <= end; i++)  #define repd(i, a, b) for (register int i = a, end = b; i >= end; i--)  #define chkmax(a, b) a = max(a, b)  #define chkmin(a, b) a = min(a, b)  #define INF (1<<30)  #define pb push_back  #define mp(a, b) make_pair(a, b)  #define fst first  #define snd second  #define pii pair<int, int>    char s[15];    namespace _998244353 {      int N;      ull P;      ull v;        inline void inc(ull &a, ull b, ull p) {          a += b;          if (a >= p) a -= p;      }        ull Mult(ull a, ull b, ull p) {          ull res = 0;          for (ull k = a; b; inc(k, k, p), b >>= 1)              if (b & 1) inc(res, k, p);          return res;      }        ull qpow(ull a, ull b, ull p) {          ull res = 1;          for (register ull k = a; b; k = Mult(k, k, p), b >>= 1)          if (b & 1) res = Mult(res, k, p);          return res;      }        inline ull read() {          ull w = 0; char c;          while (!isdigit(c = getchar())) ;          while (isdigit(c)) w = ((w << 3) + (w << 1) + (c ^ 48)) % (P-1), c = getchar();          return w;      }      void main(ull orz) {          P = orz;          scanf("%d", &N);          rep(i, 1, N) {              v = read();              printf("%llun", qpow(19, v, P));          }      }  }    namespace WA {      int N;      int ans[55246+45699+5];      void main() {          scanf("%d", &N);          ans[0] = 1;          rep(i, 1, 55246+45699) {              ans[i] = (int)(ans[i-1]*19)%998244353;          }          rep(i, 1, N) {              ll val;              scanf("%lld", &val);              if (val <= 55246+45699) printf("%dn", ans[val]);              else printf("%dn", ans[(val-55246)%45699+55246]);          }      }  }    namespace GG {      int qpow(int a, int b, int p) {          int res = 1;          for (register int k = a; b; k = (ll)k*k%p, b >>= 1)              if (b & 1) res = (ll)res * k % p;          return res;      }      void run1(int l, int r, int p) {          if (p == 998244353) {              rep(i, l, r) if (qpow(i, 499122176, 998244353) != 1 && qpow(i, 142606336, 998244353) != 1 && qpow(i, 58720256, 998244353) != 1) printf("g"); else printf(".");          } else {              rep(i, l, r)                  if (qpow(i, 757671828, 1515343657) != 1 && qpow(i, 505114552, 1515343657) != 1 &&                      qpow(i, 378552, 1515343657) != 1 && qpow(i, 96072, 1515343657) != 1) printf("g"); else printf(".");          }          puts("");      }      int st[13123120];      void run2(int p) {          memset(st, 0, sizeof(st));          int g = 6, cnt = 0;          do {              cnt++;              if (cnt % 2 && cnt % 3 && cnt % 5 && cnt % 7 && cnt % 11 && cnt % 13 && cnt % 19 && cnt % 23) st[g] = 1;              g = g*6%p;          } while (g != 6);          rep(i, 1, 13123110) if (st[i]) printf("g"); else printf(".");          puts("");      }  }    namespace PP {      inline ll Mult(ll a, ll b, ll p) {          ll c = (ll)a*b - (ll)((ull)((long double)a*b/p)*p);          return c < 0 ? c+p : ((ull)c >= (ull)p ? c-p : c);      }        ll qpow(ll a, ll b, ll p) {          ll res = 1;          for (register ll k = a; b; k = Mult(k, k, p), b >>= 1)              if (b & 1) res = Mult(res, k, p);          return res;      }      int test[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};      bool MR(ll P, int cnt = 10) {          ll s = P-1; int t = 0;          while (!(s & 1)) s >>= 1, t++;          rep(i, 0, cnt-1) {              if (P == test[i]) return true;              if (test[i] > P) return false;              ll a = qpow(test[i], s, P), nxt;              rep(x, 1, t) {                  nxt = Mult(a, a, P);                  if (nxt == 1 && a != 1 && a != P-1) return false;                  a = nxt;                  if (a == 1) break;              }              if (a != 1) return false;          }          return true;      }      int N;      void main() {          scanf("%d", &N);          while (N--) {              ll l, r;              scanf("%lld%lld", &l, &r);              while (l <= r) {                  if (MR(l)) printf("p"); else printf(".");                  l++;              }              puts("");          }      }  }    namespace UU {      int N;      int check[1000005], p[100000];      void init() {          memset(check, 0, sizeof(check));          p[0] = 0;          rep(i, 2, 1000000) {              if (!check[i]) p[++p[0]] = i;              for (register int j = 1; j <= p[0] && i*p[j] <= 1000000; j++) {                  check[i*p[j]] = 1;                  if (!(i % p[j])) break;              }          }      }      ll frac[1000001], mu[1000001];      bool issqr(ll x) {          ll v = sqrt(x);          if (v*v == x || (v-1)*(v-1)==x || (v+1)*(v+1)==x) return true;          return false;      }  #define cc(x) ((x) == 0 ? '0' : ((x) < 0 ? '-' : '+'))      void main() {          init();          scanf("%d", &N);          while (N--) {              ll l, r;              scanf("%lld%lld", &l, &r);              rep(i, 0, r-l) mu[i] = frac[i] = 1;              rep(i, 1, p[0]) {                  ll x = 1ll*p[i]*p[i], st = l-(l-1)%x-1+x;                  while (st <= r) {                      mu[st-l] = 0; frac[st-l] = st; st += x;                  }                  x = p[i], st = l-(l-1)%x-1+x;                  while (st <= r) {                      mu[st-l] = -mu[st-l];                      if (frac[st-l] != st) frac[st-l] *= x;                      st += x;                  }              }              for (register ll i = l; i <= r; i++) {                  ll val = i/frac[i-l];                  if (val == 1) printf("%c", cc(mu[i-l]));                  else if (PP::MR(val, 2)) printf("%c", cc(-mu[i-l]));                  else if (issqr(val)) printf("0");                  else printf("%c", cc(mu[i-l]));              }              puts("");          }      }  }    int main() {      srand(time(0));      scanf("%s", s);      if (s[2] == '9') _998244353::main(998244353);      if (s[1] == '?') {          if (s[2] == '+') {              _998244353::main(5211600617818708273ll);          } else {              _998244353::main(1145141);          }      }      if (s[1] == 'w') {          WA::main();      }      if (s[1] == 'g') {          int l, r, p, N;          if (s[2] == '?') {              scanf("%d", &N);              while (N--) {                  scanf("%d%d", &l, &r);                  if (N) scanf("%d", &p); else p = 1515343657;                  GG::run1(l, r, p);              }          } else {              scanf("%d", &N);              while (N--) {                  scanf("%d%d%d", &l, &r, &p);                  if (p == 998244353) GG::run1(l, r, p);                  else GG::run2(p);              }          }      }      if (s[1] == 'p') {          PP::main();      }      if (s[1] == 'u') {          UU::main();      }        return 0;  }