fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define fast ios::sync_with_stdio(false); cin.tie(nullptr);
  5. #define ll long long
  6. #define endl '\n'
  7. #define all(v) (v).begin(), (v).end()
  8. #define rall(v) (v).rbegin(), (v).rend()
  9.  
  10. const int oo = 1e9;
  11. const ll INF = 1e18;
  12. const ll MOD = 1e9+7;
  13. const int N = 10;
  14. ll dp[N+1];
  15.  
  16. long long binpow(long long a, long long b, long long m) {
  17. a %= m;
  18. long long res = 1;
  19. while (b > 0) {
  20. if (b & 1)
  21. res = res * a % m;
  22. a = a * a % m;
  23. b >>= 1;
  24. }
  25. return res;
  26. }
  27.  
  28.  
  29. void solve(){
  30. for(int i=N ; i>=1 ; i--){
  31. dp[i] = binpow(2 , N/i , MOD) - 1;
  32. for(ll j = 2*i ; j<=N ; j+=i){
  33. dp[i]-=dp[j];
  34. }
  35. }
  36. for(int i=1 ; i<=N ; i++){
  37. cout<<dp[i]<<"\n";
  38. }
  39. }
  40.  
  41. int main(){
  42.  
  43. fast
  44.  
  45. int t = 1; //cin >> t;
  46.  
  47. while(t--) solve();
  48. }
  49.  
  50. /*
  51.  * at least and exact
  52.  * 1 2 3 4 5 6 7 8 9 10
  53.  * gcd = 10 -> 2^(10/10)-1 = 1 -> {10}
  54.  * gcd = 9 -> 2^(10/9)-1 = 1 -> {9}
  55.  * gcd = 8 -> 2^(10/8)-1 = 1 -> {8}
  56.  * gcd = 7 -> 2^(10/7)-1 = 1 -> {7}
  57.  * gcd = 6 -> 2^(10/6)-1 = 1 -> {6}
  58.  * gcd = 5 -> 2^(10/5)-1 - gcd(10) = 3-1 = 2 -> {5} {5 10}
  59.  * gcd = 4 -> 2^(10/4)-1 - gcd(8) = 3-1 = 2 -> {4} {4 8}
  60.  * gcd = 3 -> 2^(10/3)-1 - gcd(6) - gcd(9) = 7-1-1 = 5 -> {3} {3 6} {3 9} {6 9} {3 6 9}
  61.  * gcd = 2 -> 2^(10/2)-1 - gcd(4) - gcd(6)-gcd(8) - gcd(10) = 31-2-1-1-1 = 26
  62.  */
Success #stdin #stdout 0s 5320KB
stdin
Standard input is empty
stdout
983
26
5
2
2
1
1
1
1
1