两道数论题(素数筛)

插图

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,但发现自己不再像去年那么惧怕这题。很开心。

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

❤采之欲遗谁,所思在远道。❤
0%