QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139620 | #5503. Euclidean Algorithm | ammardab3an | ML | 1ms | 3476kb | C++20 | 3.0kb | 2023-08-14 05:02:09 | 2023-08-14 05:02:10 |
Judging History
answer
// By AmmarDab3an
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define ll int64_t
// typedef unsigned int uint;
// typedef long long int ll;
// typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> iii;
typedef pair<ll, pll> lll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define freopenI freopen("input.txt", "r", stdin);
#define freopenO freopen("output.txt", "w", stdout);
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int x, int y) {
return uniform_int_distribution<int>(x, y)(rng);
}
int mul(int a, int b){
int ret = (1ll * (a%MOD) * (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int add(int a, int b){
int ret = (1ll * (a%MOD) + (b%MOD)) % MOD;
return (ret+MOD)%MOD;
}
int pow_exp(int n, int p){
if(!p) return 1;
if(p&1) return mul(n, pow_exp(n, p-1));
int tmp = pow_exp(n, p/2);
return mul(tmp, tmp);
}
int inv(int x){
return pow_exp(x, MOD-2);
}
const int MAX = 2e5 + 10;
const int NMAX = 2e5 + 10;
const int MMAX = 2e5 + 10;
const int LOG_MAX = ceil(log2(double(NMAX)));
const int BLOCK = ceil(sqrt(double(NMAX)));
int fac[NMAX], ifac[NMAX];
void init(){
fac[0] = 1;
for(int i = 1; i < NMAX; i++){
fac[i] = mul(fac[i-1], i);
}
ifac[NMAX-1] = inv(fac[NMAX-1]);
for(int i = NMAX-2; i >= 0; i--){
ifac[i] = mul(ifac[i+1], i+1);
}
}
int choose(int n, int c){
assert(n >= c);
return mul(fac[n], mul(ifac[c], ifac[n-c]));
}
long long solve(long long n)
{
long long s = sqrtl(n);
long long ret = 0;
for (int i = 1; i <= s; ++ i)
{
ret += n / i;
}
ret *= 2;
ret -= s * s;
return ret;
}
int brute_force(int n){
int ans = 0;
for(int i = 1; i <= n; i++)
for(int g = 1; g <= n; g++){
if(g*i > (n-g)) break;
// g*(k*i+1) <= n
// k*i+1 <= n/g
// k*i <= n/g -1
// k <= (n/g -1) / i
// k <= (n-g)/(g*i)
ans += (n-g) / (g*i);
// for(int k = 1; g*(k*i+1) <= n; k++){
// ans++;
// }
}
return ans;
}
int32_t main(){
fastIO;
#ifdef LOCAL
freopenI;
freopenO;
#endif
// freopen("name.in", "r", stdin);
// init();
int t; cin >> t; while(t--){
int n;
cin >> n;
vpii tmp;
int cur = n;
int pst = 0;
while(cur >= 1){
int cnt = n/cur - pst;
tmp.push_back({cur, cnt});
pst = n/cur;
cur = n/(n/cur + 1);
}
int ans = 0;
for(auto [a, b] : tmp){
ans += b * solve(a-1);
}
// cout << brute_force(n) << endl;
cout << ans << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3476kb
input:
3 2 5 14
output:
1 9 62
result:
ok 3 lines
Test #2:
score: -100
Memory Limit Exceeded
input:
3 29107867360 65171672278 41641960535