fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef signed long long ll;
  5. const ll mod = 1e9 + 7;
  6. ll k, dp[101][2][2][9 * 105];
  7.  
  8. ll solve(int pos, int top, int first, int prod, char str[], int sz){
  9. 	if(pos == sz) return (prod == k);
  10. 	if(dp[pos][top][first][prod] != -1) return dp[pos][top][first][prod];
  11. 	ll Ans = 0;
  12. 	int lim = top ? (str[pos] - '0') : 9;
  13. 	for(int i = 0; i<=lim; i++){
  14. 		if(!first && i == 0){
  15. 			Ans =  (Ans + solve(pos + 1, top && (i == lim), first || (i != 0), prod, str, sz) % mod) % mod;
  16. 		}else{
  17. 			Ans = (Ans + solve(pos + 1, top && (i == lim), first || (i != 0), prod * i, str, sz) % mod) % mod;
  18. 		}
  19. 	}
  20. 	return dp[pos][top][first][prod] = Ans % mod;
  21. }
  22.  
  23. int main() {
  24. 	int t;
  25. 	char A[105], B[105];
  26.  
  27. 	scanf("%d", &t);
  28. 	for(int i = 1; i<=t; i++){
  29. 		scanf("%s %s %lld", A, B, &k);
  30.  
  31. 		ll tmp = k;
  32. 		while(tmp % 2 == 0) tmp/=2;
  33. 		while(tmp % 3 == 0) tmp/=3;
  34. 		while(tmp % 5 == 0) tmp/=5;
  35. 		while(tmp % 7 == 0) tmp/=7;
  36.  
  37. 		if(k > 900 || tmp > 1){
  38. 			printf("Case %d: 0\n", i);
  39. 			continue;
  40. 		}
  41. 		ll Ans = 0;
  42. 		memset(dp, -1, sizeof(dp));
  43. 		Ans = solve(0, 1, 0, 1, B, strlen(B)) % mod;
  44. 		memset(dp, -1, sizeof(dp));
  45. 		Ans = (Ans - solve(0, 1, 0, 1, A, strlen(A)) % mod) % mod;
  46.  
  47. 		int val = 1;
  48. 		for(int j = 0; j<strlen(A); j++){
  49. 			val *= (A[j] - '0');
  50. 		}
  51.  
  52. 		Ans += ((ll)val == k);
  53. 		if(Ans < 0) Ans += mod;
  54. 		printf("Case %d: %lld\n", i, Ans % mod);
  55. 	}
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 6452KB
comments (?)
stdin
copy 
2
1 9 3
7 37 6
stdout
copy 
Case 1: 1
Case 2: 3
https://ideone.com/wXDPi3
language:
C++14 (gcc 8.3)
created:
8 years 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!