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

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

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

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

我想换个脑子%%%

A

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

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

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

#include <stdio.h>

typedef long long LL;

const int _N = 10001000;

LL phi[_N], P[_N];
bool mark[_N];

void Euler(LL mx)
{
    LL cnt = 0;
    phi[1] = 1;
    for (LL i = 2; i <= mx; ++i) {
        if (!mark[i]) P[++cnt] = i, phi[i] = i-1;
        for (LL j = 1; j <= cnt && i*P[j] <= mx; ++j) {
            mark[i*P[j]] = true;
            if (!(i % P[j])) { phi[i*P[j]] = phi[i] * P[j]; break; }
            phi[i*P[j]] = phi[i] * (P[j]-1);
        }
    }
    return;
}

int main()
{
    LL n, m;
    scanf("%lld%lld", &n, &m);
    Euler(n);
    while (m--) {
        LL t;
        scanf("%lld", &t);
        if (t == 1) { printf("0 "); continue; }
        printf("%lld ", t-1-phi[t]);
    }
    return 0;
}

B

用插板法考虑，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 .

#include <stdio.h>

typedef long long LL;

const LL _P = 1000000007LL;

LL mul(LL t1, LL t2)
{
    LL ans = 0;
    t1 %= _P;
    while (t2) {
        if (t2 & 1) ans = (ans+t1) % _P;
        t2 >>= 1, t1 = (t1<<1) % _P;
    }
    return ans;
}

LL mont(LL t1, LL t2)
{
    LL ans = 1;
    t1 %= _P;
    while (t2) {
        if (t2 & 1) ans = mul(ans, t1);
        t2 >>= 1, t1 = mul(t1, t1);
    }
    return ans;
}

int main()
{
//    2^(n-1) mod P
    LL n;
    char tt;
    while ((tt = getchar()) < '0' || tt > '9');
    n = tt - '0';
    while ((tt = getchar()) >= '0' && tt <= '9')
        n = (n*10%(_P-1) + tt-'0') % (_P-1);
    printf("%lld
", mont(2, n-1));
    return 0;
}

C

设 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 ，答案是其中的最小值

#include <stdio.h>

typedef long long LL;

void exgcd(LL t1, LL t2, LL &x, LL &y, LL &d)
{
    if (t2) { exgcd(t2, t1%t2, y, x, d); y -= t1/t2*x; return; }
    x = 1, y = 0, d = t1;
    return;
}

int main()
{
    LL n, t, p1, p2, a, b, x, y;

    scanf("%lld%lld%lld%lld%lld", &n, &p1, &a, &p2, &b);
    exgcd(a, b, x, y, t);
    if (n % t) { printf("-1
"); return 0; }

    x = x*n/t, y = y*n/t, a /= t, b /= t;
    LL tx = (x%b + b) % b;
    LL ty = y - (tx-x)/b * a;
    if (ty < 0) { printf("-1
"); return 0; }
    LL ans = tx*p1 + ty*p2;
    
    while (ty >= 0) {
        if (ans > tx*p1 + ty*p2)
            ans = tx*p1 + ty*p2;
        tx += b, ty -= a;
    }

    printf("%lld", ans);
    return 0;
}

D

紫书原题。观察发现求的实际上是 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 是一个答案

#include <stdio.h>

typedef long long LL;

const int _N = 20000000;

LL ans[_N], A[_N], P[_N], G[_N];

void add(LL v)
{
    for (LL i = 2; i*i <= v; ++i)
        while (!(v % i)) v /= i, ++A[i];
    if (v != 1) ++A[v];
    return;
}

void del(LL v)
{
    for (LL i = 2; i*i <= v; ++i)
        while (!(v % i)) v /= i, --A[i];
    if (v != 1) --A[v];
    return;
}

int main()
{
    LL n, m, up, dn, cnt = 0, Gcnt = 0;
    scanf("%lld%lld", &n, &m);
    dn = n-1;
    //init P
    LL v = m;
    for (LL i = 2; i*i <= v; ++i) {
        if (!(v % i)) G[++Gcnt] = i;
        while (!(v % i)) v /= i, ++P[i];
    }
    if (v != 1) ++P[v], G[++Gcnt] = v;
    
    for (up = 1; up <= dn; ++up) {
        add(dn-up+1);
        del(up);
        LL i;
        for (i = 1; i <= Gcnt; ++i)
            if (P[G[i]] > A[G[i]]) break;
        if (i == Gcnt+1)
            ans[++cnt] = up;
    }
    printf("%lld
", cnt);
    for (up = 1; up <= cnt; ++up)
        printf("%lld ", ans[up]+1);
    return 0;
}

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

题目:

A老队友

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

评测说明 : 1s,最大规模的数据1.3s

问题描述

新年快到了，南开信竞队的队员们从全国各地聚到了一起，共来了N个人。何老板按照一种奇特的算法把它们从1到N编号。使得对于编号i的队员，如果编号j队员跟他是老队友，那么j一定满足下列两个条件：
1. 1<=j<i；
2. i和j之间存在一个>1的公约数；

在聚会现场，何老板提了M个问题，形如：x号同学的老队友有几个？
对于何老板的每个提问，请你做出回答。
在诸位大神级的前辈面前，你要回答得又快又准，错了小心被打手板。

输入格式

第一行，两个整数N和M
接下来一行，M个空格间隔的整数，表示何老板的M个询问

输出格式

一行，M个空格间隔的整数，依次对应每个问题的答案

样例输入 1

12 3
6 10 11

样例输出 1

3 5 0

样例输入 2

30 5
5 28 3 10 2

样例输出 2

0 15 0 5 0

提示

对于30%的数据:1<=N,M<=1000
对于100%的数据:1<=N<=10000000   1<=M<=100000   

B整数拆分

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

评测说明 : 时限1000ms

问题描述

给你一个正整数N，F(x)表示把N拆分成x个正整数之和的方案数。
例如，当n=5时：
F(1)=1,方案为：{5}
F(2)=4,方案为：{1+4}  {4+1}  {2+3}  {3+2}
F(3)=6,方案为：{1+1+3}  {1+3+1}  {3+1+1}  {1+2+2}  {2+1+2}  {2+2+1} 
F(4)=4,方案为：{1+1+1+2}  {1+1+2+1}  {1+2+1+1}  {2+1+1+1}  
F(5)=1,方案为：{1+1+1+1+1} 
请你计算出F(1)+F(2)+......+F(N)
结果可能很大，mod 1,000,000,007 再输出!

输入格式

第一行，一个整数N

输出格式

一行，一个整数，表示所求的结果

样例输入 1

5

样例输出 1

16

样例输入 2

8

样例输出 2

128

提示

对于50%的数据1<=N<=100
对于100%的数据1<=N<=10100000

C观光车

时间限制 : 10000 MS   空间限制 : 65536 KB

问题描述

何老板带领n名游客来到一景区大门口，需要乘坐观光车游览景区。

景区提供两种观光车，一种是每辆车可以坐a名游客，包一辆车费用是p1块钱；另一种每辆车可以坐b名游客，包一辆车费用是p2块钱。

何老板想让这n名游客都坐上观光车，且每辆车都坐满。问何老板至少要花费多少钱？

输入格式

第一行，一个整数n,表示游客的总数。

第二行，两个空格间隔的整数，表示p1和a

第三行，两个空格间隔的整数，表示p2和b

输出格式

一行，一个整数，表示所需最少费用。

如果无解，输出“-1”

样例输入 1

43
1 3
2 4

样例输出 1

15

样例输入 2

40
5 9
5 12

样例输出 2

-1

样例输入 3

486
25 27
33 36

样例输出 3

446

提示

样例1说明：第一种车13辆，第二种车1辆

1 <= n,a,b,p1,p2 <= 2,000,000,000

Dspark搭塔

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

评测说明 : 1s

问题描述

Spark用积木搭了n座塔，第i座塔的高度为ai.
他发明了一种有趣增高操作：每一次他都会从1到n,在第i(i<n)座塔的上面再搭上一个和第i+1座塔一样高的塔，第n座塔没法增高，只好扔掉了。这样做了一次之后Spark就只剩下了n-1座塔(n的值变为n-1)。于是他很有耐心的重复了许多次，直到最后只剩下了一座塔，设它的高度为H。
Spark很迷信，他有一个幸运数字m，于是他把H%m当成最终的美观度。

他惊奇的发现，最开始n座塔中有一些塔的高度不论是多少，最终的美观度都不会变！他想知道哪些塔的高度不会影响美观度。

输入格式

一行两个整数n,m ( 1<=n<=100 000, 2<=m<=10^9).

对30%的数据 n<=30,m<=100

输出格式

第一行一个整数N，表示不影响美观度的塔的个数。

第二行N个整数，第i个数 bi 表示第 bi  座塔的高度不影响美观度，请从小到大输出 bi。

样例输入 1

3 2

样例输出 1

1 
2

样例输入 2

7 6

样例输出 2

2
2 6

提示

样例解释：
第一次操作后变成 a1 + a2, a2 + a3.

第二次操作后变成 a1 + 2a2 + a3.

又因为m=2，最终的美观度显然与 a2。没有关系.