fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<ll,ll>ii;
  5. const ll mod=1e9+7;
  6. ii dp[20][5433][181];
  7. ll kq,l,r,coso[20];
  8. vector<int>dg;
  9. int q,k,P[11];
  10. bool lcm[5433][181];
  11.  
  12. ii get(int pos,int sum1,int sum2,bool dabe)
  13. {
  14.     // first là tổng còn second là số lượng
  15.     if(pos==-1&&(lcm[sum1][sum2]))return ii{0,1};else
  16.         if(pos==-1)return ii{0,0};
  17.     if(dp[pos][sum1][sum2]!=ii{-1,0}&&dabe)return dp[pos][sum1][sum2];
  18.     ii res={0,0};
  19.     for(int i=0;i<=max(dg[pos],dabe*9);i++)
  20.     {
  21.         ii cc=get(pos-1,sum1+P[i],sum2+i,dabe|(i<dg[pos]));
  22.         res.first=((res.first+cc.first)%mod+((i*coso[pos])%mod*(cc.second%mod))%mod)%mod;
  23.         res.second+=cc.second;
  24.     }
  25.     if(dabe)dp[pos][sum1][sum2]=res;
  26.     return res;
  27. }
  28.  
  29. ll call(ll x)
  30. {
  31.     if(x==0)return 0;
  32.     dg.clear();
  33.     for(;x>0;x/=10)dg.push_back(x%10);
  34.     return get(dg.size()-1,0,0,0).first;
  35. }
  36.  
  37. int main()
  38. {
  39.     ios::sync_with_stdio(0);
  40.     cin.tie(NULL);
  41.     cout.tie(NULL);
  42.     coso[0]=1;
  43.     P[0]=0;
  44.     for(int i=1;i<=9;i++)P[i]=i*i+P[i-1];
  45.     for(int i=1;i<=18;i++)coso[i]=coso[i-1]*10%mod;
  46.     for(int i=0;i<=5432;i++)for(int j=0;j<=180;j++)
  47.         if(__gcd(i,j)==1)lcm[i][j]=1;
  48.             else lcm[i][j]=0;
  49.     for(int i=0;i<=19;i++)for(int j=0;j<=5432;j++)for(int k=0;k<=180;k++)dp[i][j][k]={-1,0};
  50.     cin>>q;
  51.     for(int i=1;i<=q;i++)
  52.     {
  53.         cin>>l>>r;
  54.         cout<<(call(r)-call(l-1)+mod*mod)%mod<<"\n";
  55.     }
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.1s 311804KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GKZH8r
language:
C++14 (gcc 8.3)
created:
176 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!