数论-某寒假训练赛 Round1 (Feb, 2018)-白红宇

数论-某寒假训练赛 Round1 (Feb, 2018)

阅读量：5174 次

发布时间：2019-06-13

本文共 7144 字，大约阅读时间需要 23 分钟。

没什么难题，很水的一场训练赛。C题卡了很久，因为背错了通解公式，过不了样例。然后D题就没足够时间写正解了，交了个暴力，30分。

正确的通解方式打开方式：x = x' + k*b/gcd(a, b)

脑子短路时想到的公式：x = x' + k*b

我想换个脑子%%%

这题完全违背生活常识，i 是 j 的老队员时 j 却不是 i 的老队员。

小于 x 且不与 x 互质（即有 >1 的公约数）的数有 x-1-phi(x) 个。

考虑到询问次数 M 比较大，先用线性欧拉晒把 N 以内的 phi 计算出来。

1 #include 
      
        2  3 typedef long long LL; 4  5 const int _N = 10001000; 6  7 LL phi[_N], P[_N]; 8 bool mark[_N]; 9 10 void Euler(LL mx)11 {12     LL cnt = 0;13     phi[1] = 1;14     for (LL i = 2; i <= mx; ++i) {15         if (!mark[i]) P[++cnt] = i, phi[i] = i-1;16         for (LL j = 1; j <= cnt && i*P[j] <= mx; ++j) {17             mark[i*P[j]] = true;18             if (!(i % P[j])) { phi[i*P[j]] = phi[i] * P[j]; break; }19             phi[i*P[j]] = phi[i] * (P[j]-1);20         }21     }22     return;23 }24 25 int main()26 {27     LL n, m;28     scanf("%lld%lld", &n, &m);29     Euler(n);30     while (m--) {31         LL t;32         scanf("%lld", &t);33         if (t == 1) { printf("0 "); continue; }34         printf("%lld ", t-1-phi[t]);35     }36     return 0;37 }

View Code

用插板法考虑，F(x) = C(n-1, x-1)

F(1) + F(2) + ... + F(n) = 2^n-1

答案为 2^n-1 mod p （p = 1,000,000,007, 是一个素数）

n 很大。考虑到 p 是素数且 gcd(2, p) = 1, 由费马小定理 2^p-1 ≡ 1 (mod p)

也就是说一堆 2 乘起来模 p 的时候，每有 p-1 个 2，就会模出一个 1 ，对结果没有影响。

所以 2^n-1 mod p = 2^{(n-1) mod (p-1)} mod p （其实就是用欧拉函数降幂的一种特殊情况）

对于 (n-1) mod (p-1) , 由模运算法则，可以从最低位起对 n-1 取模，对结果没有影响。也就是一边读入一边模。

然后再用 Montgomery 算 2^{(n-1) mod (p-1)} mod p .

1 #include 
      
        2  3 typedef long long LL; 4  5 const LL _P = 1000000007LL; 6  7 LL mul(LL t1, LL t2) 8 { 9     LL ans = 0;10     t1 %= _P;11     while (t2) {12         if (t2 & 1) ans = (ans+t1) % _P;13         t2 >>= 1, t1 = (t1<<1) % _P;14     }15     return ans;16 }17 18 LL mont(LL t1, LL t2)19 {20     LL ans = 1;21     t1 %= _P;22     while (t2) {23         if (t2 & 1) ans = mul(ans, t1);24         t2 >>= 1, t1 = mul(t1, t1);25     }26     return ans;27 }28 29 int main()30 {31 //    2^(n-1) mod P32     LL n;33     char tt;34     while ((tt = getchar()) < '0' || tt > '9');35     n = tt - '0';36     while ((tt = getchar()) >= '0' && tt <= '9')37         n = (n*10%(_P-1) + tt-'0') % (_P-1);38     printf("%lld\n", mont(2, n-1));39     return 0;40 }

View Code

设 1 号车租 x 辆， 2号车租 y 辆得

ax + by = n

由贝祖定理设 t = gcd(a, b) , 则 t 应为 n 的约数，否则无解。

然后用扩欧算出一组 x', y'

得到原方程特解 x = x' * n / t, y = y' * n / t

通解 xx = x + k*b/t , yy = y - k*a/t

显然合法的 xx, yy >= 0

那先求出 xx 最小整数解 xx = (x mod (b/t) + (b/t)) mod (b/t)

红色式子中, k = xx-x*t/b

把上式代入蓝色式子的 k 中 yy = y - (xx-x*t/b)*a/t

这样算出来 x 的最小整数解 xx 时对应的 yy，如果 yy < 0 就无解（因为若要yy增大，则xx必定减小，而此时xx已经是最小整数解，减小后就为负数了）

否则依次计算

xx₂ = xx + k*b/t , yy₂ = yy- k*a/t

xx3 = xx₂ + k*b/t, yy₃ = yy₂ - k*a/t

...

(满足 yy >= 0)

计算 xx*p1 + yy*p2 ，答案是其中的最小值

1 #include 
      
        2  3 typedef long long LL; 4  5 void exgcd(LL t1, LL t2, LL &x, LL &y, LL &d) 6 { 7     if (t2) { exgcd(t2, t1%t2, y, x, d); y -= t1/t2*x; return; } 8     x = 1, y = 0, d = t1; 9     return;10 }11 12 int main()13 {14     LL n, t, p1, p2, a, b, x, y;15 16     scanf("%lld%lld%lld%lld%lld", &n, &p1, &a, &p2, &b);17     exgcd(a, b, x, y, t);18     if (n % t) { printf("-1\n"); return 0; }19 20     x = x*n/t, y = y*n/t, a /= t, b /= t;21     LL tx = (x%b + b) % b;22     LL ty = y - (tx-x)/b * a;23     if (ty < 0) { printf("-1\n"); return 0; }24     LL ans = tx*p1 + ty*p2;25     26     while (ty >= 0) {27         if (ans > tx*p1 + ty*p2)28             ans = tx*p1 + ty*p2;29         tx += b, ty -= a;30     }31 32     printf("%lld", ans);33     return 0;34 }

View Code

紫书原题。观察发现求的实际上是 C(n-1, i) (0 <= i <= n-1) 里是 m 倍数的数，对应的一个答案是 i+1.

即如果 m | C(n-1, i) , 一个答案为 i+1.

C有一个递推公式 C(i, j) = C(i, j-1) * (i - j + 1) / j ，易证；而 C(i, 0) = 1。

得到 30 分的方法：枚举 C(b-1, i)

考虑到 C 的值可能比较大，根据唯一分解定理一定可以把它用它的素因数相乘的方式表示。

比如 18 = 2 * 3 * 3

开一个巨大的数组，A[i] 表示当前计算到的 C 的分解式中素因数 i 的数量

P[i] 表示 m 的素因数 i 的数量。然后还需要把 m 的素因数提前记录到 G 中，比如当 m = 18 , G = {2, 3}

每次推到一个新的 Ci 时根据乘或除对 A[i] 进行更新。

然后枚举 m 的素因数 G[t] .

如果对于所有 t, 均有 P[G[t]] <= A[G[t]] 说明 i+1 是一个答案

1 #include 
      
        2  3 typedef long long LL; 4  5 const int _N = 20000000; 6  7 LL ans[_N], A[_N], P[_N], G[_N]; 8  9 void add(LL v)10 {11     for (LL i = 2; i*i <= v; ++i)12         while (!(v % i)) v /= i, ++A[i];13     if (v != 1) ++A[v];14     return;15 }16 17 void del(LL v)18 {19     for (LL i = 2; i*i <= v; ++i)20         while (!(v % i)) v /= i, --A[i];21     if (v != 1) --A[v];22     return;23 }24 25 int main()26 {27     LL n, m, up, dn, cnt = 0, Gcnt = 0;28     scanf("%lld%lld", &n, &m);29     dn = n-1;30     //init P31     LL v = m;32     for (LL i = 2; i*i <= v; ++i) {33         if (!(v % i)) G[++Gcnt] = i;34         while (!(v % i)) v /= i, ++P[i];35     }36     if (v != 1) ++P[v], G[++Gcnt] = v;37     38     for (up = 1; up <= dn; ++up) {39         add(dn-up+1);40         del(up);41         LL i;42         for (i = 1; i <= Gcnt; ++i)43             if (P[G[i]] > A[G[i]]) break;44         if (i == Gcnt+1)45             ans[++cnt] = up;46     }47     printf("%lld\n", cnt);48     for (up = 1; up <= cnt; ++up)49         printf("%lld ", ans[up]+1);50     return 0;51 }

View Code

考试地址:http://oi.nks.edu.cn/zh/Contest/Details/83

题目:

A老队友

时间限制 : - MS 空间限制 : 165536 KB