fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. LL dp[22][81 * 20][9 * 20][2];
  5. LL F(LL x)
  6. {
  7.  
  8.     char str[20];
  9.     sprintf(str,"%lld",x);
  10.     int N = strlen(str) , i , j , k , l , m;
  11.     dp[N][0][0][1] = 1;
  12.  
  13.     for(i=N-1;i>=0;--i)
  14.         for(j=0;j<=81*(N-i);++j)
  15.             for(k=0;k<=(9*(N-i));++k)
  16.                 for(l=0;l<2;++l)
  17.                     {
  18.                         dp[i][j][k][l] = 0;
  19.                         for(m=0;m<=(l?9:str[i]-'0');++m)
  20.                             if(j>=m*m && k>=m)
  21.                                 dp[i][j][k][l]+=dp[i+1][j-m*m][k-m][l || m<str[i]-'0'];
  22.                     }
  23.     LL ret = 0;
  24.  
  25.     for(j=0;j<=81*(N);++j)
  26.         for(k=0;k<=(9*(N));++k)
  27.             if(__gcd(j,k)==1)
  28.                 ret+=dp[0][j][k][0];
  29.  
  30.     for(i=N-1;i>=0;--i)
  31.         for(j=0;j<=81*(N-i);++j)
  32.             for(k=0;k<=(9*(N-i));++k)
  33.                 for(l=0;l<2;++l)
  34.                         dp[i][j][k][l] = 0 ;
  35.     dp[N][0][0][1] = 0;
  36.     return ret;
  37. }
  38.  
  39.  
  40. int main()
  41. {
  42.  
  43.     int T;
  44.     scanf("%d",&T);
  45.     for(;T;--T)
  46.     {
  47.         LL A , B ;
  48.         scanf("%lld%lld",&A,&B);
  49.         printf("%lld\n",F(B+1)-F(A));
  50.     }
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0s 102976KB
comments (?)
stdin 
1
5 15
stdout 
3
https://ideone.com/62awhH
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 years ago
visibility:
secret

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!