fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3. #include <cmath>
  4. #include <iostream>
  5. using namespace std;
  6. typedef long long ll;
  7. #define bye return
  8. #define yes cout << "YES" << el;
  9. #define no cout << "NO" << el;
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. #include <ext/pb_ds/tree_policy.hpp>
  12. using namespace __gnu_pbds;
  13. #define Shoyo                     \
  14. ios_base::sync_with_stdio(0); \
  15. cin.tie(NULL);
  16. #define ff first
  17. #define ss second
  18. #define pii pair<ll, ll>
  19. #define all(v) v.begin(), v.end()
  20. #define allr(v) v.rbegin(), v.rend()
  21. #define cl(x, y) (x + y - 1) / y
  22. #define el "\n"
  23. #define os tree<pii, null_type, less<>, \
  24. rb_tree_tag, tree_order_statistics_node_update>
  25. ll dx[4] = {-1, 0, 1, 0};
  26. ll dy[4] = {0, 1, 0, -1};
  27. const ll LOG = 20;
  28. const int N = 1e6 + 5;
  29. const ll MOD = 1e9 + 7;
  30. bool is_prime[200];   // عشان نجيب البرايمز
  31. vector<int> primes;
  32. void sieve(int mx) {
  33.     fill(is_prime + 2, is_prime + mx + 1, true);
  34.     for (int i = 2; i * i <= mx; i++) {
  35.         if (is_prime[i]) {
  36.             for (int j = i * i; j <= mx; j += i)
  37.                 is_prime[j] = false;
  38.         }
  39.     }
  40.     for (int i = 2; i <= mx; i++) {
  41.         if (is_prime[i]) primes.push_back(i);
  42.     }
  43. }
  44. string l,r;
  45. ll vid;
  46. ll v[20][2][2][165][165];
  47. ll mem[20][2][2][165][165];
  48. ll p;
  49. ll dp(ll i,ll le,ll ri,ll sum,ll rem) {
  50.    if (i==r.size()) {
  51.        return (sum==p and rem==0 );
  52.    }
  53.     if (sum>p)return 0;
  54.     ll &res=mem[i][le][ri][sum][rem];
  55.     if (v[i][le][ri][sum][rem]==vid) return res;
  56.     v[i][le][ri][sum][rem]=vid;
  57.     ll st=le?0:l[i];
  58.     ll e=ri?9:r[i];
  59.     res=0;
  60.     for (ll d=st;d<=e;d++) {
  61.         res+=dp(i+1,le or( d>l[i]), ri or (d<r[i]),sum+d,(rem*10+d)%p);
  62.     }
  63. return res;
  64.  
  65. }
  66. void solve() {
  67.     cin>>l>>r;
  68.     l=string(r.size()-l.size(),'0')+l;
  69.     ll ans=0;
  70.     for (auto &x:l)x-='0';
  71.     for (auto &x:r)x-='0';
  72.     sort(all(primes));
  73.    for (auto z:primes) {
  74.        p=z;
  75.        if (p>167)break;
  76.        vid++;
  77.        ans+=dp(0,0,0,0,0);
  78.    }
  79. cout<<ans<<el;
  80.  
  81. }
  82. int main(){
  83.     Shoyo;
  84.     ll t = 1;
  85.  cin>>t;
  86.     sieve(200);
  87.     while (t--)
  88.     {
  89.         solve();
  90.     }
  91.     return 0;
  92. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/YNw6NC
language:
C++ (gcc 8.3)
created:
10 hours 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!