Project Euler 134

This is a simple problem, even when it has $45\%$ of difficult rating, even the code is short. There are no many concepts involved, just modular operations.

Statement

Consider the consecutive primes $p_1 = 19$ and $p_2 = 23$. It can be verified that $1219$ is the smallest number such that the last digits are formed by $p_1$ whilst also being divisible by $p_2$.

In fact, with the exception of $p_1 = 3$ and $p_2 = 5$, for every pair of consecutive primes $p_2 > p_1$, there exist values of $n$ for which the last digits are formed by $p_1$ and $n$ is divisible by $p_2$. Let $S$ be the smallest of these values of $n$.

Find $\sum S$ for every pair of consecutive primes with $5 \leq p_1 \leq 1000000$.

Solution

Let’s take a look to the number that ends with the digits of $p_1$:

\begin{aligned} \overline{n p_{1}} = n\cdot 10^{\lfloor \log_{10} p_{1}\rfloor + 1} + p_{1} \end{aligned}

by the condition of the problem, this number should be divisible by $p_2$:

\begin{aligned} n\cdot 10^{\lfloor \log_{10} p_{1}\rfloor + 1} + p_{1} &\equiv 0 \mod p_{2}\cr n &\equiv -p_{1}\cdot \mathrm{inv}\big(10^{\lfloor \log_{10} p_{1}\rfloor + 1}\big) \mod p_{2} \end{aligned}

since the problem requires to find the minimum number, $n$ must be the smallest positive value that satisfies the above equation.

The time complexity of this solution is $\mathcal{O}(N\log\log N + \pi(N)\log(N))$, where the value of $\pi(N)$ could be bounded by $x/\ln(x)$, so the time complexity is: $\mathcal{O}(N\log\log N + N)$

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define N 1000205

bitset <N> primes;
vector <pair<int, int> > p;

ll fastexp(ll x, ll y, ll p){
    ll ans = 1;
    while(y > 0){
        if(y&1) ans = (ans*x)%p;
        y >>= 1;
        x = (x*x)%p;
    }
    return ans%p;
}

ll inv(ll x, ll p){
    return fastexp(x, p-2, p);
}

void sieve(){
    int prev = 10;
    for(int i=2; i<N; i++){
        if(!primes[i]){
            if(i > prev) prev *= 10;
            p.push_back({i, prev});
            for(ll j=1LL*i*i; j<N; j+=i) primes[j] = 1;
        }
    }
}


int main(){
    sieve();
    ll ans = 0;
    for(int i=2; i<p.size()-1; i++){
        if(p[i].first > 1000000) break;
        int p1 = p[i].first;
        int p2 = p[i+1].first;
        int n = (1LL*inv(p[i].second, p2)*(p2 - p1)) % p2;
        if(n <= 0) n += p2;
        ans += 1LL*n*p[i].second + p[i].first;
    }
    cout << ans << '\n';
    return 0;
}

it runs on 20ms in my computer.