Prime pair connection (Project Euler 134)

题目大意：

对于连续的质数$p1$, $p2$, 满足$5 <= p1 <= 1000000$ 求出最小的整数$S$, 它以 $p1$结尾并且能够被$p2$整除。求$S$的和。

思路：

只需要知道对于一对$p1$, $p2$怎么求对应的$S$. 把$S$表示成$x*10^k+p1$ 其中$k$是$p1$的长度。

然后就转化为求同余方程 $x*10^k+p1equiv 0 (mod p2)$

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <set>
 6 #include <cstring>
 7 #include <map>
 8 #include <queue>
 9 using namespace std;
10 
11 typedef long long ll;
12 #define N 10000000
13 #define M 1100
14 typedef pair<int,int> pii;
15 
16 
17 bool flag[N];
18 int p[N],phi[N];
19 
20 
21 void Get_Primes(int lim)
22 {
23     phi[1]=1;
24     for (int i=2;i<=lim;i++)
25     {
26         if (!flag[i]) p[++p[0]]=i,phi[i]=i-1;
27         for (int j=1;j<=p[0] && i*p[j]<=lim;j++)
28         {
29             flag[i*p[j]]=true;
30             if (i%p[j]==0) 
31             {
32                 phi[i*p[j]]=phi[i]*p[j];
33                 break;
34             }
35             else phi[i*p[j]]=phi[i]*(p[j]-1);
36         }
37     }
38 }
39 
40 ll Power(ll x, ll P, ll mod)
41 {
42     ll res = 1;
43     for (; P ; P >>= 1)
44     {
45         if (P & 1) res = res * x % mod;
46         x = x * x % mod;
47     }
48     return res;
49 }
50 
51 
52 ll Solve(ll p1, ll p2)
53 {
54     ll tmp = p1, t = 1;
55     while (tmp) tmp /= 10, t *= 10;
56     ll x = (p2 - p1) * Power(t, p2 - 2, p2) % p2; 
57     return x * t + p1;
58 }
59 
60 int main()
61 {
62     freopen("in.in","r",stdin);
63     freopen("out.out","w",stdout);
64 
65     ll res = 0;
66     Get_Primes(10000000); 
67     for (int i = 3; p[i] <= 1000000; ++i) res += Solve(p[i], p[i + 1]);
68     cout << res << endl;
69     return 0;
70 }

View Code

答案：18613426663617118