fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define pll pair<ll,ll>
  8. #define pb push_back
  9. #define emb emplace_back
  10. #define lg(x) __lg(x)
  11. #define all(s) s.begin(),s.end()
  12. #define name "test"
  13. #define Mask(i) (1LL<<i)
  14. #define testbit(mask, i) ((mask >> i) & 1LL)
  15. #define onBit(mask, i) (mask | (1LL << i))
  16. #define offBit(mask, i) (mask & ~(1LL << i))
  17. #define flipBit(mask, i) (mask ^ (1LL << i))
  18. #define showbit(mask, x) bitset<x>(mask)
  19. const ll mod = 1e9 + 7;
  20.  
  21. void add(ll &a, ll b){
  22.      if((a += b) >= mod) a -= mod;
  23. }
  24.  
  25.  
  26. const ll inf = 1e18;
  27. const ll lim = 1e7 + 5;
  28. const ll N = 2e5 + 5;
  29.  
  30. int a[15];
  31. bool check[1000005];
  32.  
  33. int d[1000005];
  34. ll dp[1000005];
  35. int main()
  36. {
  37.      ios_base::sync_with_stdio(0);
  38.      cout.tie(0);cin.tie(0);
  39.  
  40.      int n, k; cin >> n >> k;
  41.      for(int i = 1; i <= k; i++) cin >> a[i];
  42.  
  43.      int cnt = 1;
  44.      for(int i = 1; i <= k; i++){
  45.           int num = a[i];
  46.           for(int j = 1; j <= sqrt(num); j++){
  47.                if(num % j == 0){
  48.                     if(check[j] == false){
  49.                          check[j] = true;
  50.                          d[cnt] = j;
  51.                          cnt++;
  52.                     }
  53.  
  54.                     if(num / j != j){
  55.                          if(check[num / j] == false){
  56.                               check[num / j] = true;
  57.                               d[cnt] = num / j;
  58.                               cnt++;
  59.                          }
  60.                     }
  61.                }
  62.           }
  63.      }
  64.      cnt--;
  65. //     for(int i = 1; i <= cnt; i++) cout << d[i] << " ";
  66.  
  67.      dp[1] = 1;
  68.      for(int i = 1; i <= n; i++){
  69.           for(int j = 1; j <= cnt; j++){
  70.                int jump = d[j];
  71.  
  72.                dp[i + jump] = (dp[i + jump] + dp[i]) % mod;
  73.           }
  74.      }
  75.  
  76.      cout << dp[n];
  77. }
  78.  
  79.  
  80.  
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
Success #stdin #stdout 0s 5740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7xXt30
language:
C++14 (clang 8.0)
created:
1 hour 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!