Submission #16713

#TimeUsernameProblemLanguageResultExecution timeMemory
16713gs14004Xtreme gcd sum (kriii2_X)C++14
1 / 4
4000 ms40900 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <limits.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <utility> #include <bitset> #include <iostream> using namespace std; typedef long long lint; typedef long double llf; typedef pair<int, int> pi; const int mod = 1e9 + 7; int che[1000005]; int moebius[1000005]; int n, a[10005], b[10005], rng[10005]; lint cnt[1000005]; lint mod_inv(int x, int p){ lint ret = 1, piv = x; while(p){ if(p&1) ret *= piv; piv *= piv; ret %= mod; piv %= mod; p >>= 1; } return ret; } const int maxp = 1e6; void get_moebius(){ for(int i=2; i<=maxp; i++){ for(int j=i; j<=maxp; j+=i){ if(!che[j]) che[j] = i; } } for(int i=1; i<=maxp; i++){ int cnt = 0, lst = -1; int x = i; while(x > 1){ if(lst == che[x]){ cnt = -1; break; } lst = che[x]; x /= lst; cnt++; } if(cnt < 0) continue; moebius[i] = cnt % 2 ? -1 : 1; } } vector<int> change[1000005]; int main(){ scanf("%d",&n); fill(cnt, cnt + maxp + 1, 1); for(int i=0; i<n; i++){ scanf("%d %d",&a[i], &b[i]); int pos = 1, cur = -1; int nxt_update = 1; while(pos <= maxp){ if(nxt_update == pos){ cur = b[i] / pos - (a[i] - 1) / pos; nxt_update = 1e9; int T = b[i] / pos - 1; if(T >= 0){ int s = (b[i] + T + 1) / (T + 1); if(s > pos) nxt_update = min(nxt_update, s); } T = (a[i] - 1) / pos - 1; if(T >= 0){ int s = (a[i] + T) / (T + 1); if(s > pos) nxt_update = min(nxt_update, s); } } cnt[pos] *= cur; cnt[pos] %= mod; pos++; } } get_moebius(); lint ret = 0; for(int i=1; i<=maxp; i++){ for(int j=1; i*j<=maxp; j++){ ret += 1ll * i * moebius[j] * cnt[i * j] % mod; ret %= mod; } } ret += mod; ret %= mod; printf("%lld",ret); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...