fork download 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. const int N = 1e6 + 5;
  8. const int MOD = 1e9 + 7;
  9. int l, r, ans = 0;
  10. int POW10[19];
  11. void add(int &u, int v) {
  12.     u += v;
  13.     if (u >= MOD) u -= MOD;
  14. }
  15. vector<int> primes;
  16. bool isPrime[N];
  17. void sieve(int n) {
  18.     for (int i = 2; i <= n; i++) if (!isPrime[i]) {
  19.         primes.push_back(i);
  20.         for (int j = i * i; j <= n; j += i) isPrime[j] = 1;
  21.     }
  22. }
  23.  
  24. int getLen(int a) {
  25.     int len = 0;
  26.     while(a) {
  27.         len ++;
  28.         a /= 10;
  29.     }
  30.     return len;
  31. }
  32.  
  33. namespace sub1 {
  34. int calc(int p1, int p2) {
  35.     int base = POW10[getLen(p1)];
  36.     int tx = 1;
  37.     while(1) {
  38.         if ((tx * base + p1) % p2 == 0) break;
  39.         tx++;
  40.     }
  41.     return ((tx * base) % MOD + p1) % MOD;
  42. }
  43. void solve() {
  44.     for (int i = 1; i < primes.size(); i++) {
  45.         int p1 = primes[i - 1], p2 = primes[i];
  46.         if (p1 < l || p2 > r) continue;
  47.         add(ans, calc(p1, p2));
  48.     }
  49.     cout << ans;
  50. }
  51. };
  52. inline int MUL(int a, int p, int mod) {
  53.     int ans = 0;
  54.     for (; p > 0; p >>= 1, a = a * 2 % mod) if (p & 1) ans = (ans + a) % mod;
  55.     return ans;
  56. }
  57. inline int POW(int a, int p, int mod) {
  58.     int ans = 1 % mod;
  59.     for (; p > 0; p >>= 1, a = MUL(a, a, mod)) if (p & 1) ans = MUL(ans, a, mod);
  60.     return ans;
  61. }
  62.  
  63. inline int gcdex(int a, int b, int c) {
  64.     int x = c * POW(a, b - 2, b);
  65.     int rem = x / b;
  66.     x = x - rem * b;
  67.     return x;
  68. }
  69. inline int calc(int p1, int p2) {
  70.     int a = POW10[getLen(p1)];
  71.     int c = p2 - p1;
  72.     int x = gcdex(a, p2, c);
  73.     // cerr << x << " " << a << '\n';
  74.     return (MUL(x, a, MOD) + p1) % MOD;
  75. }
  76.  
  77. namespace subfull {
  78. bool nok[N];
  79. void solve() {
  80.     memset(nok, 0, sizeof(nok));
  81.     for (int p: primes) {
  82.         for (int i = ((l + p - 1) / p) * p; i <= r; i += p) {
  83.             if (i != p) nok[i - l] = 1;
  84.         }
  85.     }
  86.     vector<int> newPrimes;
  87.     for (int i = l; i <= r; i++) {
  88.         if (!nok[i - l]) newPrimes.push_back(i);
  89.     }
  90.     // for (int i: newPrimes) cerr << i << " "; cerr << "\n";
  91.     for (int i = 1; i < newPrimes.size(); i++) {
  92.         int p1 = newPrimes[i - 1], p2 = newPrimes[i];
  93.         if (p1 < l || p2 > r) continue;
  94.         add(ans, calc(p1, p2));
  95.     }
  96.     cout << ans;
  97. }
  98. };
  99. signed main() {
  100.     cin.tie(NULL)->sync_with_stdio(false);
  101.     if(ifstream("SUFPRI.inp")) {
  102.         freopen("SUFPRI.inp", "r", stdin);
  103.         freopen("SUFPRI.out", "w", stdout);
  104.     }
  105.     sieve(1000001);
  106.     POW10[0] = 1; for (int i = 1; i <= 18; i++) POW10[i] = POW10[i - 1] * 10;
  107.     cin >> l >> r;
  108.     if (r <= 1000) return sub1::solve(), 0;
  109.     return subfull::solve(), 0;
  110.     return 0;
  111. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/FiTpSk
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!