Editorial for Tổng các ước chung lớn nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
#include<iostream> #include<algorithm> #include<cstdio> #include<vector> #define fr(a,b,c) for (a=b;a<=c;a++) #define maxn 1000000 using namespace std; int f[maxn+10]; long long sumf[maxn+10]; vector<int> a; void etf() { int i,j; fr(i,1,maxn) f[i]=i; fr(i,2,maxn) { if (f[i]==i) for (int j=i;j<=maxn;j+=i) f[j]=f[j]/i*(i-1); sumf[i]=sumf[i-1]+f[i]; } } long long gcdsum(int n) { int i,d; long long re=0; a.clear(); a.push_back(0); fr(i,1,n) if (n/i<i) break; else { a.push_back(i); if (n/i!=i) a.push_back(n/i); } sort(a.begin(),a.end()); fr(i,1,int(a.size())-1) re+=sumf[n/a[i]]*(a[i]+a[i-1]+1)*(a[i]-a[i-1])/2; return re; } int main() { etf(); int n; while (1) { scanf("%d",&n); if (!n) break; printf("%lld\n",gcdsum(n)); } return 0; }
Code mẫu của RR
#include <sstream> #include <cassert> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <iomanip> #include <algorithm> #include <vector> #include <set> #include <stack> #include <map> #include <string> #include <queue> #include <bitset> using namespace std; #define int long long #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i) #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i) #define REP(i, a) for (int i = 0, _a = (a); i < _a; ++i) #define REPD(i,n) for(int i = (n)-1; i >= 0; --i) #define DEBUG(X) { cerr << #X << " = " << (X) << endl; } #define PR(A, n) { cerr << #A << " = "; FOR(_, 1, n) cerr << A[_] << ' '; cerr << endl; } #define PR0(A, n) { cerr << #A << " = "; REP(_, n) cerr << A[_] << ' '; cerr << endl; } #define sqr(x) ((x) * (x)) #define ll long long #define double long double typedef pair<int, int> II; #define PI (2 * acos((double)0)) #define __builtin_popcount __builtin_popcountll #define SZ(x) ((int)(x).size()) #define ALL(a) (a).begin(), (a).end() #define MS(a,x) memset(a, x, sizeof(a)) #define next ackjalscjaowjico #define prev ajcsoua0wucckjsl #define y1 alkscj9u20cjeijc #define y0 u9cqu3jioajc double safe_sqrt(double x) { return sqrt(max((double)0.0, x)); } int GI(int& x) { return scanf("%lld", &x); } const int MN = 1000111; int phi[MN], f[MN]; void init() { int N = 1000 * 1000; // phi[i] = cnt(x: 1 <= x <= i && gcd(x, i) == 1) FOR(i,1,N) phi[i] = i; FOR(i,2,N) if (phi[i] == i) for(int j = i; j <= N; j += i) phi[j] -= phi[j] / i; // f[i] = cnt(x, y: 1 <= x, y <= i && gcd(x, y) == 1) f[1] = 0; FOR(i,2,N) f[i] = f[i-1] + phi[i]; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout << (fixed) << setprecision(9); init(); int n; while (GI(n) == 1 && n) { int s = 0; for(int i = 1; i <= n; ) { int q = n / i; int r = n / q; s += (r - i + 1) * (i + r) / 2 * f[q]; i = r + 1; } cout << s << '\n'; } }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> //#include <fstream> #include <cstring> #include <stdlib.h> #include <math.h> #include <algorithm> #define Max 1000000 using namespace std; long long G[1000001]; int num_primes,a[100000],m,u,isprime[1000001]; int gcd(int a,int b) { int r; while(b!=0) { r = a%b; a = b; b = r; } return a; } int main() { //freopen("GCDSUM.in","r",stdin); int p[100000]; memset(isprime,1,sizeof(isprime)); //printf("%d",isprime[10]); for(int i = 2;i<=1000;i++) if(isprime[i]) { for(int j = 2*i;j<=Max;j+=i) isprime[j] = 0; } num_primes = 0; for(int i = 2;i<=Max;i++) if(isprime[i]) { p[++num_primes] = i; } /* for(int i = 1;i<=num_primes;i++) { a[i] = p[i]; if(a[i]>1000); else { while(a[i]<=Max) a[i] = (a[i])*p[i]; a[i] = a[i]/p[i]; } } */ //printf("%d\n",num_primes); //printf("%d",g[78498]); for(int i=1;i<=num_primes;i++) { G[p[i]]=p[i]-1; for(int j=p[i]+p[i];j<=Max;j+=p[i]) { if(G[j]!=0) continue; m=j/p[i]; if(G[m]==0) continue; int u = p[i],v = j/p[i]; while(v%p[i]==0) { v=v/p[i];u=u*p[i];} G[j]=G[m]*p[i]+(p[i]-1)*m+G[(j/u)]*(p[i]-1)*(u/p[i]); } } //printf("%d\n",num_primes); for(int i=2;i<=Max;i++) G[i]+=G[i-1]; int n; while(scanf("%d",&n)>0 && n>0) { printf("%lld\n",G[n]); } //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} Program GCDSUM; Const input = ''; output = ''; maxn = 1000000; Var fi,fo: text; p,g: array [1..maxn] of integer; f: array [1..maxn] of int64; n: integer; Procedure openfile; Begin Assign(fi, input); Reset(fi); Assign(fo, output); Rewrite(fo); End; Procedure primegens; Var i,k: integer; Begin Fillchar(p, sizeof(p), 0); For i:= 2 to maxn do if p[i] = 0 then Begin k:= 2 * i; While k <= maxn do Begin p[k]:= i; k:= k + i; End; End; End; Procedure gens; Var i,tmp,pw: integer; Begin g[1]:= 1; For i:= 2 to maxn do if p[i] = 0 then g[i]:= 2 * i - 1 else Begin tmp:= i; pw:= 0; While tmp mod p[i] = 0 do Begin tmp:= tmp div p[i]; inc(pw); End; If tmp = 1 then g[i]:= (pw + 1) * i - pw * i div p[i] else g[i]:= g[tmp] * g[i div tmp]; End; f[1]:= 0; For i:= 2 to maxn do f[i]:= f[i - 1] + g[i] - i; End; Procedure closefile; Begin Close(fo); Close(fi); End; Begin primegens; gens; openfile; Repeat Readln(fi, n); If n <> 0 then writeln(fo, f[n]); Until n = 0; closefile; End.
Comments