fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define all(v) v.begin(), v.end()
  5.  
  6. void setIO(string name = ""){
  7.     ios_base::sync_with_stdio(0);
  8.     cin.tie(0);
  9.  
  10.     if (!name.empty()) {
  11.         freopen((name + ".inp").c_str(), "r", stdin);
  12.         freopen((name + ".out").c_str(), "w", stdout);
  13.     }
  14.  
  15. }
  16.  
  17. const ll MOD = 1e9 + 7;
  18. const int MAXN = 1e8+1;
  19.  
  20. ll ans[MAXN+1];
  21.  
  22. void solve() {
  23.     int n; cin >> n;
  24.     cout << ans[n] << endl;
  25. }
  26.  
  27. void build() {
  28.     ans[1] = 0;
  29.     ans[2] = 1;
  30.  
  31.     ll psum = 2, npsum = 1;    
  32.     ll ppos = 1, nppos = 1;
  33.     for (int i = 3; i < MAXN; i++) {
  34.         if (ans[i] == i) {
  35.             ppos++;
  36.             psum += i;
  37.             ans[i] = ans[i-1] + nppos*i - npsum;
  38.             ans[i] %= MOD;
  39.         }
  40.         else {
  41.             nppos++;
  42.             npsum += i;
  43.             ans[i] = ans[i-1] + ppos*i - psum;
  44.             ans[i] %= MOD;
  45.         }   
  46.     }
  47. }
  48.  
  49. int main() {
  50.     setIO("pnpdiff");
  51.     int t = 1;
  52.  
  53.     for (int i = 2; i <= MAXN; i++) {
  54. 		if (ans[i] == 0) {
  55. 			for (int j = i; j <= MAXN; j += i) ans[j] = i;
  56. 		}
  57. 	}
  58.  
  59.     cin >> t;
  60.  
  61.     build();
  62.     while (t--) solve();
  63. }
Success #stdin #stdout 3.82s 785140KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NkAIdL
language:
C++ (gcc 8.3)
created:
2 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!