fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ld long double
  5. #define stp(n) fixed<<setprecision(n)
  6. #define flash cin.tie(0); cin.sync_with_stdio(0);
  7. #define el '\n'
  8. #define Point pair<double, double>   // Define Point as a pair of doubles
  9.  
  10. using namespace std;
  11.  
  12. //
  13. //#pragma GCC optimize("03")
  14. //#pragma GCC target("tune=native")
  15. //#pragma GCC optimize("unroll-loops")
  16.  
  17.  
  18.  
  19. int dp[55][1 << 15];
  20. int primes[15] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
  21. int bin[55];
  22.  
  23. int solve(int rem, int msk) {
  24.     if (rem == 0)return 1;
  25.     int &ans = dp[rem][msk];
  26.     if (~ans)return ans;
  27.     ans = 0;
  28.     for (int i = 1; i <= rem; i++) {
  29.         if ((bin[i] & msk) == 0) {
  30.             ans += solve(rem - i, bin[i] | msk);
  31.         }
  32.     }
  33.     return ans;
  34. }
  35.  
  36. void testCase() {
  37.  
  38.     for (int i = 1; i <= 50; i++) {
  39.         int msk = 0;
  40.         for (int j = 0; j < 15; ++j)
  41.             if (i % primes[j] == 0)msk |= (1 << j);
  42.         bin[i] = msk;
  43.     }
  44.     memset(dp, -1, sizeof dp);
  45.     int l, r;
  46.     cin >> l >> r;
  47.     int ans = 0;
  48.  
  49.     for (int i = l; i <= r; i++) {
  50.         ans += solve(i,0);
  51.     }
  52.     cout << ans;
  53.  
  54. }
  55.  
  56. int main() {
  57.  
  58.     //freopen("dotak.in", "r", stdin);
  59.     //   freopen("output.txt", "w", stdout);
  60.  
  61.     flash;
  62.     int t = 1;
  63.     //  cin >> t;
  64.     while (t--) {
  65.         testCase();
  66.     }
  67.  
  68. }
Success #stdin #stdout 0.01s 10612KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/sJZD64
language:
C++ (gcc 8.3)
created:
17 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!