/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 26ms 532.0 KiB
#2 Accepted 11ms 532.0 KiB
#3 Time Exceeded ≥1099ms ≥532.0 KiB
#4 Time Exceeded ≥1099ms ≥344.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
 
 
// const int MOD = 1e9 + 7;
const int MX = 1e6;
long long dp[MX + 1];
long long divisors[MX + 1];
 

// unordered_map<int,long long> mp;

// long long again_solve(int n) {
//     if(mp[n]) return mp[n];
//     long long res = 0;
//     long long i = 1;
//     while (i <= n) {
//         long long q = n / i;
//         long long j = n / q;
//         res += q * (j - i + 1);
//         i = j + 1;
//     }
//     return mp[n] = res;
// }
 
 
// void solve(){
//   int n;
//   cin >> n;
//   cout << again_solve(n) - n << endl;
// }

void solve(){
  long long n;
  cin >> n;
  long long ans = 0;
  for(int i = 1 ; i <= min((long long)1e6,n) ; i++){
    ans += n / i - 1;
  }
  if(n <= 1e6){
    cout << ans << endl;
    return;
  }
  for(int i = n / (int)1e6 + 1 ; i >= 1 ; i--){
    ans += max(0ll,(n / i - max((long long)1e6+1,n / (i + 1))));
  }
  // if(n <= MX) cout << dp[n] << endl;
  // else{
  //   long long ans = dp[MX] - (n - MX);
  //   int j = MX + 1;
  //   while(n / j == n / MX){
  //     ans += n / j;
  //     j++;
  //   }
  //   cout << ans << endl;
  //   for(int k = n / j ; k >= 1 ; k--){
  //     ans += k * (n / k - n / (k + 1));
  //   }
  //   cout << ans << endl;
  // }
  cout << long(ans - (n - 1e6) + 1) << endl;
}



 
 
 
 
int main()
{
    int t = 1;
    cin >> t;
    while(t--) solve();
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1207 D2. GCD equal Absolute Value (Hard Version)
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-14 19:04:11
Judged At
2025-07-14 19:04:11
Judged By
Score
5
Total Time
≥1099ms
Peak Memory
≥532.0 KiB