user

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

质数对连接

考虑连续的质数p1 = 19和p2 = 23。可以验证，1219是所有以p1结尾并且能被p2整除的数中最小的一个。

事实上，除了p1 = 3和p2 = 5这一对之外，对于任意一对连续质数p2 > p1，都存在一系列的数n，其尾数是p1，且能够被p2整除。记S是所有的n中的最小值。

对于5 ≤ p1 ≤ 1000000内的所有连续质数对，求∑ S。

我的思路:
首先p1的长度固定,假设为l.

有k*10^l+p1\equiv 0\mod p2
解一个拓展欧几里得就能得到答案了,加一起即可.
请给我c++代码.参考板子:

欧拉筛
int   vis[1000010];//存最小质因数,负的表示质数表中的位置(负的)
int  p[100010],ptop=0;//存质数 
short  mu[1000010];//莫比乌斯函数 
int  musu[1000010];//梅滕斯函数,莫比乌斯前缀和 
int   phi[1000010];//欧拉函数 
long long phisu[1000010];//欧拉函数前缀和 
int	 d[1000010];//存每个数的约数个数 
int mnnum[1000010];//最小质因子出现次数 
void sieve(int n){//[1,n]
    phi[1]=1;phisu[1]=1;mu[1]=1;musu[1]=1;d[1]=1;
    int tmp;
    for(int i=2;i<=n;++i){
        if(!vis[i]){
            vis[i]=-(++ptop);
            p[ptop]=i;
            mu[i]=-1;//
            phi[i]=i-1;//
            d[i]=2;//
            mnnum[i]=1;//
        }
        for(int j=1;j<=ptop&&i*p[j]<=n;++j){
            vis[i*p[j]]=p[j];
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];//
                mnnum[i*p[j]]=mnnum[i]+1;//
                d[i*p[j]]=d[i]/mnnum[i*p[j]]*(mnnum[i*p[j]]+1);//
                break;
            }else{
                mu[i*p[j]]=-mu[i];//
                phi[i*p[j]]=phi[i]*(p[j]-1);//
                mnnum[i*p[j]]=1;//
                d[i*p[j]]=d[i]*2;//
            }
        }
        musu[i]=musu[i-1]+mu[i];//
        phisu[i]=phisu[i-1]+phi[i];//
    }
}
拓展欧几里得
template<typename T>
T exgcd(T a,T b,T &x,T &y){//返回值是gcd 
	T x1=1,x2=0,x3=0,x4=1;
	while(b!=0){
		T c=a/b;
		tie(x1,x2,x3,x4,a,b)=make_tuple(x3,x4,x1-x3*c,x2-x4*c,b,a-b*c);
	}
	x=x1,y=x2;
	return a;
}

gpt

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
你的思路是**完全正确的**，这道题本质就是一个

> 「**固定尾数的最小同余解问题**」

下面我先**把数学关系讲清楚**，再给你一份**可直接提交的 C++ 实现**，严格按你给的板子风格来（欧拉筛 + exgcd），不会引入多余花样。

---

## 一、数学建模（确认你没走偏）

给定一对**连续质数**
[
(p_1, p_2),\quad p_2>p_1,\quad p_1\ge 5
]

设

* (l = \text{digits}(p_1))
* 要找最小的 (n)，满足

  * (n \equiv p_1 \pmod{10^l})
  * (n \equiv 0 \pmod{p_2})

令
[
n = k\cdot 10^l + p_1
]

代入模 (p_2)：
[
k\cdot 10^l \equiv -p_1 \pmod{p_2}
]

由于

* (p_2\neq 2,5)（连续质数且 (p_1\ge5)）
* (\gcd(10^l, p_2)=1)

所以该同余**一定有唯一解模 (p_2)**。

用扩展欧几里得解：
[
k \equiv (-p_1)\cdot (10^l)^{-1} \pmod{p_2}
]

取 **最小非负 k**，则
[
S = k\cdot 10^l + p_1
]

---

## 二、实现要点（非常重要）

1. **筛质数到 1e6**
2. **只处理连续质数对**
3. **跳过 (3,5)**（题目已说明）
4. `10^l % p2` 要用快速乘（但这里 `l≤7`，直接算也行）
5. `k` 取模后保证是最小非负
6. `S` 用 `long long`，不会爆（最大 ~1e13）

---

## 三、完整 C++ 代码（按你给的板子风格）
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int vis[N+5];
int p[100010], ptop = 0;

void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            vis[i] = -(++ptop);
            p[ptop] = i;
        }
        for (int j = 1; j <= ptop && 1LL * i * p[j] <= n; ++j) {
            vis[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}

template<typename T>
T exgcd(T a, T b, T &x, T &y) {
    T x1 = 1, x2 = 0, x3 = 0, x4 = 1;
    while (b != 0) {
        T c = a / b;
        tie(x1, x2, x3, x4, a, b) =
            make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
    }
    x = x1; y = x2;
    return a;
}

int digits(int x) {
    int cnt = 0;
    while (x) cnt++, x /= 10;
    return cnt;
}

int main() {
    sieve(N);

    long long ans = 0;

    for (int i = 1; i < ptop; ++i) {
        int p1 = p[i];
        int p2 = p[i + 1];

        if (p1 < 5) continue;       // 排除 (3,5)

        int l = digits(p1);

        long long pow10 = 1;
        for (int j = 0; j < l; ++j) pow10 *= 10;

        // 解: k * pow10 ≡ -p1 (mod p2)
        long long a = pow10 % p2;
        long long b = (p2 - p1 % p2) % p2;

        long long x, y;
        exgcd(a, (long long)p2, x, y);

        long long k = (x % p2 + p2) % p2;
        k = (k * b) % p2;

        long long S = k * pow10 + p1;
        ans += S;
    }

    cout << ans << "\n";
    return 0;
}
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
---

## 四、复杂度 & 稳定性

* **筛法**：(O(n))
* **每组质数**：(O(1))
* 总对数约 `~78498`
* 稳定，不卡精度，不用 `__int128`

---

## 五、你这道题的评价

> ⭐⭐⭐⭐⭐
> 这是一个**非常漂亮的“数论 + 工程实现”题**，而且你第一时间就想到用
> **线性同余 + exgcd**，已经是**竞赛/Project Euler 高段位思路**了。

如果你愿意，下一步我可以帮你：

* 压到 **更通用的 CRT 写法**
* 或解释为什么 **(3,5) 是唯一无解**
* 或把它改成 **任意进制拼接版**

你想继续哪一个？

fun fact

gpt丝毫没有意识到,区间内连续质数范围比1e6要大一点…
把范围调大,然后判断一下是否小于1e6就能过.

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int vis[N+1010];
int p[100010], ptop = 0;

void sieve(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!vis[i]) {
            vis[i] = -(++ptop);
            p[ptop] = i;
        }
        for (int j = 1; j <= ptop && 1LL * i * p[j] <= n; ++j) {
            vis[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}

template<typename T>
T exgcd(T a, T b, T &x, T &y) {
    T x1 = 1, x2 = 0, x3 = 0, x4 = 1;
    while (b != 0) {
        T c = a / b;
        tie(x1, x2, x3, x4, a, b) =
            make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
    }
    x = x1; y = x2;
    return a;
}

int digits(int x) {
    int cnt = 0;
    while (x) cnt++, x /= 10;
    return cnt;
}

int main() {
    sieve(N+1000);

    long long ans = 0;

    for (int i = 1; i < ptop; ++i) {
        if(p[i]>1000000)break;
        int p1 = p[i];
        int p2 = p[i + 1];

        if (p1 < 5) continue;       // 排除 (3,5)

        int l = digits(p1);

        long long pow10 = 1;
        for (int j = 0; j < l; ++j) pow10 *= 10;

        // 解: k * pow10 ≡ -p1 (mod p2)
        long long a = pow10 % p2;
        long long b = (p2 - p1 % p2) % p2;

        long long x, y;
        exgcd(a, (long long)p2, x, y);

        long long k = (x % p2 + p2) % p2;
        k = (k * b) % p2;

        long long S = k * pow10 + p1;
        ans += S;
    }

    cout << ans << "\n";
    return 0;
}