fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std ; 
  3.  
  4.  
  5. #define ll long long 
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define fir first 
  8. #define sec second 
  9. #define pill pair < ll , ll >
  10. #define FOR( i , a , b ) for (ll i = (a) , _b = (b) ; i <= _b ; i ++ )  
  11. #define FORR( i , a , b ,c ) for (ll i = (a) , _b = (b) ; i <= _b ; i +=(c) )  
  12. #define pb push_back 
  13. #define str string 
  14. #define ALL(a) (a).begin() , (a).end() 
  15. #define rep( i , a , b) for (ll i = (a) ; i < (b) ; i ++ )
  16. #define ld long double
  17. const ll maxn = 1e3;
  18. #define debug 0
  19. #define oo (ll)(1e18)
  20. bool check_nt[85] ;
  21. int NT[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83 } ;
  22. bool nt ( ll n ) {
  23.  
  24. 	return check_nt[n] ;
  25. }
  26. bool check( ll s){
  27. 	str k = to_string(s );
  28. 	ll d = 0 ; 
  29. 	for (auto x : k) 
  30. 	{
  31. 		d += x -'0' ;
  32. 	}
  33. 	return (nt(d)) ;
  34. }
  35.  
  36. str L , R ;
  37.  
  38. ll l , r , k ;	
  39. bitset<10000> f[13][3][3][85] ;
  40. bool ok = 0 ;
  41. str ans_1 ;
  42. void dfs ( int i , int ok_l , int ok_r , int sum , int du , str ans  , int n ){
  43. 	// cerr << i << ' ' << ok_l << ' ' << ok_r << ' ' << sum << ' ' << du << ' ' << ans << '\n' ;
  44. 	// cout << ans << '\n' ;
  45. 	if ( ok ) return ;
  46. 	if (f[i][ok_l][ok_r][sum][du]) return ;
  47. 	f[i][ok_l][ok_r][sum][du] = 1 ;
  48. 	if ( i > n - 1) {
  49. 		// cout << ok_l << ' ' << ok_r << '\n' ;
  50. 		if (check_nt[sum] && du == 0 ) {
  51. 			// ok = 1 ;
  52. 			int run = 0;
  53. 			while ( (run + 1 )< ans.size() && ans[run] == '0' ) run ++ ;
  54.  
  55. 			str comPare = ans.substr ( run ) ;
  56.  
  57. 			if ( comPare < ans_1) ans_1 = comPare ;
  58. 			// cout << ans << '\n' ;
  59. 			return ;
  60. 		}
  61. 			// cout << ans << '\n' ;
  62. 		return ;
  63. 	}
  64. 	else {
  65.  
  66. 		int low = ok_l ? ( '0' ) : L[i] ;
  67. 		int high= ok_r ? ( '9' ) : R[i];
  68. 		low = max ( low , (( i == 0 ) ? 49 : 48 )) ;
  69. 		// cout << i << ' ' << low << ' ' << (char)high << ' ' << ok_l << ' ' << ok_r << '\n' ;
  70. 		for ( int c = low ; c <= high ; c ++ ) {
  71.  
  72. 			// cout << c << ' ' << c - '0' << '\n' ;
  73.  
  74.  
  75. 			dfs ( i + 1 , (ok_l | ( c > L[i])) , (ok_r | ( c < R[i])) , sum + c - '0' , (du * 10 + c - '0' ) %k , ans + char(c),n ); 
  76. 		}
  77. 	}
  78. }
  79. #define name "TASK" 
  80. int main(){
  81.     fast 
  82.     if(fopen(name".INP","r")) {
  83.         freopen (name".INP","r",stdin);
  84.         freopen (name".OUT","w",stdout);
  85.     }
  86.     for (int i = 0 ; i < 23 ; i ++ )
  87.     	check_nt[NT[i]] = 1 ;
  88.     while ( cin >> l >> r >> k ) {
  89.     	ok = 0 ;
  90.     	ans_1 = "9999999999999999999999999999999" ;
  91.     	if ( k > 1e4 ){
  92.  
  93. 	    	bool c = 1 ;
  94. 			ll minest = l + ( k - ( l % k ) ) ;
  95. 			// cout << minest << '\n' ;
  96. 			vector < str > ans ;
  97.  
  98. 			FORR ( i , minest , r , k ) {
  99. 				if ( i % k == 0 ) {
  100. 					if (check(i)) {
  101. 						c = 0 ;
  102. 						ans.pb(to_string(i)) ;
  103. 						// cout << i << '\n' ; 
  104. 						// break ;
  105. 					}
  106. 				}
  107. 			}
  108. 			sort ( ALL(ans) ,[&] ( str a , str b ) {
  109. 				return a < b ;
  110. 			}) ;
  111. 			if(c)cout << -1 << '\n' ;
  112. 			else cout <<ans[0] << '\n' ;
  113.     	}
  114.     	else {
  115.  
  116.     		L = to_string ( l ); 
  117.     		// 0999999999
  118.     		// while ( L.size() <= 10 ) L = "0" + L ;
  119.     		R = to_string ( r ); 
  120.     		// while ( R.size() <= 10 ) R = "0" + R ;
  121.     		// cerr << L << ' ' << R << '\n' ;
  122.     		str OLD_L = L ;
  123.     		FOR ( i , L.size() , R.size()) {
  124.     			for (int i = 0; i < 13; ++i)
  125.    		 		for (int j = 0; j < 3; ++j)
  126.         			for (int k = 0; k < 3; ++k)
  127.             			for (int l = 0; l < 85; ++l)
  128.                				f[i][j][k][l].reset();
  129.     			L = OLD_L ;
  130.     			while ( L.size() < R.size() ) L = "0" + L ;
  131.     			dfs ( 0 , 0 , 0 , 0 , 0 , "" , i ) ;
  132.     		}
  133.  
  134.     		if (ans_1 == "9999999999999999999999999999999") cout << -1 << '\n' ; 
  135. 			else cout << ans_1 << '\n' ;
  136.  
  137.     	}
  138.  
  139.  
  140. 	}
  141.     cerr << "\nTIME: = " << (1.0*clock())/CLOCKS_PER_SEC << '\n';
  142.     return(0) ;
  143. }
Success #stdin #stdout #stderr 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
TIME: = 0.006546
https://ideone.com/ukaNyI
language:
C++14 (gcc 8.3)
created:
1 day 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!