两道数论题 (素数筛)

发表于 更新于 分类于 ， 本文字数： 5.1k 阅读时长 ≈ 9 分钟

插图

1. Remoteland (Southwestern Europe Regional Contest 2011)

Problem

Description

In the Republic of Remoteland, the people celebrate their independence day every year. However, as it was
a long long time ago, nobody can remember when it was exactly. The only thing people can remember is
that today, the number of days elapsed since their independence (D) is a perfect square, and moreover it is
the largest possible such number one can form as a product of distinct numbers less than or equal to n.
As the years in Remoteland have 1, 000, 000, 007 days, their citizens just need D modulo 1, 000, 000, 007.
Note that they are interested in the largest D, not in the largest D modulo 1, 000, 000, 007.

Input

Every test case is described by a single line with an integer n, (1 ≤ n ≤ 10, 000, 000). The input ends
with a line containing 0.

Output

For each test case, output the number of days ago the Republic became independent, modulo 1, 000, 000, 007,one per line.

Sample Input

4
9348095
6297540
0

Sample Output

4
177582252
644064736

Solution

Todo

在前 n 个数中选出一些数，使这些数的乘积为尽可能大的完全平方数。

Idea

可以将 $n!$ 做素因子分解， 例如前 $5$ 个数中， $5! = 24 = 2^3 \times 3^1$ ， 完全平方数可表示为 $a^2 = (a_1 \times a_2)^2 = a_1^2 \times a_2^2$，所以我们将 $n!$ 素因子分解后偶数次幂的项保留， 奇数次幂的幂次减 1，再求乘积即为所求答案。

此题中我们需要对这一过程进行优化，先预处理出 $n!$， 之后再依次除以全部幂次为奇数的素数即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstring>
typedef long long LL;
using namespace std;

int n;
const int MAXN = 10000007;
const int MOD = 1e9+7;

bool notprime[MAXN+1];
int prime[MAXN];
void getPrime()
{
    memset(notprime, false, true);
    memset(prime, 0, sizeof(prime));
    notprime[0] = notprime[1] = true;
    for(int i=2; i<=MAXN; i++)
    {
        if(!notprime[i])
            prime[++prime[0]] = i;
        for(int j=1; j<=prime[0]&&prime[j]<=MAXN/i; j++)
        {
            notprime[prime[j]*i] = true;
            if(i%prime[j] == 0)
                break;
        }
    }
}

LL qpow(LL a, LL b)
{
    LL res = 1;
    a = a%MOD;
    while(b)
    {
        if(b&1)
            res = res * a % MOD;
        b >>= 1;
        a = a*a%MOD;
    }
    return res;
}

/*
 * 一个之前没遇到的知识点为全局数组定义时初始化如果部分初始化
 * 如 jc[MAXN] = {1, 1}，会因为自动补0导致编译出来的文件很大
 * 这题一开始是这样写的，交上去是CE， 报错为 Complied file is too large.
 * 而且在本机编译时需要的时间也为七八秒，时间极长。
 * 一开始以为是MLE了，疯狂缩小数组大小，发现并无卵用，后来才发现是这里的问题
 */
int jc[MAXN];	

void init()
{
    jc[0] = jc[1] = 1;
    for(int i=2; i<MAXN; i++)
        jc[i] = 1LL * jc[i-1] * i % MOD;
}

int main()
{
    init();
    getPrime();
    int cnt;
    LL res = 1;
    int p, z;
    while(~scanf("%d", &n) && n)
    {
        res = 1;
        for(int i=1; i<=prime[0] && prime[i]<=n; i++)
        {
            cnt = 0;
            p = prime[i];
            z = n;
            while(z)
            {
                cnt += z/p;
                z /= p;
            }
            if(cnt & 1)
            {
                res = (res * p) % MOD;
            }
        }
        printf("%lld\n", jc[n] * qpow(res, MOD-2) % MOD);
    }
    return 0;
}

2. Counting Divisors (2017 多校联合训练第四场 HDOJ 6069)

传送门: Counting Divisors HDOJ 6069

Problem

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 3996    Accepted Submission(s): 1450

Description

In mathematics, the function $d(n)$ denotes the number of divisors of positive integer $n$.
For example, $d(12)=6$ because $1,2,3,4,6,12$ are all $12$’s divisors.
In this problem, given $l,r$ and $k$, your task is to calculate the following thing :
$\left(\sum_{i=l}^r d(i^k)\right)\bmod 998244353$

Input

The first line of the input contains an integer $T(1\leq T\leq15)$, denoting the number of test cases.
In each test case, there are $3$ integers $l,r,k(1\leq l\leq r\leq 10^{12},r-l\leq 10^6,1\leq k\leq 10^7)$.

Output

For each test case, print a single line containing an integer, denoting the answer.

Sample Input

1
2
3
4
3
1 5 1
1 10 2
1 100 3

Sample Output

1
2
3
10
48
2302

Solution

Idea

  1. 首先是 唯一分解定理 和 因子个数求法。每个大于 1 的自然数均可写为质数的积，而且这些素因子按大小排列之后，写法仅有一种方式。 其因子的个数为每个质数的幂次 + 1 后的乘积。
    比如 $100 = 2^2 \times 5^2$， 其因子的个数即为 $(2+1) \times (2+1) = 9$.
  2. 根据 1 我们不难得出一个数字的幂的因子个数， $a = {a_1}^{n_1} \times {a_2}^{n_2}… \times {a_n}^{n_n}$, 则 $a^k$ 因子个数为 $(kn_1+1) \times (kn_2+1)…… \times (ka_n+1)$。如 $100^3$ 的因子个数为 $( (2\times3+1) \times (2 \times 3 +1) )$.
  3. 这题我们可以先预先筛出 $\sqrt {r} = 10^6$ 的素数，之后依次用筛出来的每个素数 $p$ 对区间 $p$ 的倍数进行处理，看其因子中有几个 $p$，从而算出区间内每个数因子的个数。进行完前边的处理后，若区间内一个数还有素数因子没处理到，则该素数的幂次为 $1$。具体细节在代码中体现。
  4. 区间 $[l,r]$ 内第一个数字 $p$ 的倍数为 $\lfloor {l+p-1 \over p} \rfloor \times p$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
typedef long long LL;
using namespace std;

const int MAXN = 1e6+7;
LL prime[MAXN+1];
LL num[MAXN+1];
LL a[MAXN];

const LL MOD = 998244353;
LL l, r, k;

void getPrime()
{
    memset(prime, 0, sizeof(prime));
    for(int i=2; i<=MAXN; i++)
    {
        if(!prime[i])
            prime[++prime[0]] = i;
        for(int j=1; j<=prime[0] && prime[j]<=MAXN/i; j++)
        {
            prime[prime[j]*i] = 1;
            if(i%prime[j]==0)
                break;
        }
    }
}

void process()
{
    LL p, cnt;

    for(LL i=1; i<=prime[0] && prime[i] * prime[i]<=r; i++)
    {
        p = prime[i];
        for(LL j=(l+p-1)/p*p; j<=r; j+=p)
        {
            cnt = 0;
            while((a[j-l]%p==0) )
            {
                cnt++;
                a[j-l] /= p;
            }

            num[j-l] = (num[j-l] * ((k*cnt + 1) % MOD)) % MOD;
        }
    }
}


int main()
{
    getPrime();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d", &l, &r, &k);
        int len = r-l+1;
        for(int i=0; i<len; i++)
        {
            a[i] = l+i;
            num[i] = 1;
        }
        process();
        LL ans = 0;
        for(LL i=l; i<=r; i++)
        {
            if(a[i-l] > 1)
                num[i-l] = num[i-l] * (k+1) % MOD;
            ans = (ans + num[i-l]) %MOD;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

Note

这是去年多校训练时一道题目，当时觉得是自己触不可及的题目，是极难、不可能做出的。

今年队伍自己拉题训练时拉了这套题，自己竟惊奇地发现这题在自己可以做的范围内。虽然自己的一开始的算法还很笨拙，是一点点优化到 AC，但发现自己不再像去年那么惧怕这题。很开心。

或许有些事真的是水到渠成的。