LJS的GCD

題目描述

L J S LJS LJS來到了一間密室里
L J S LJS LJS為了快點與同伴們會合準備用勉強還能運行的計算機計算足夠大的 g c d gcd gcd和因為他知道只有這樣他才能用強大的資料來沖擊這件密室的門
求

	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			ans+=__gcd(i,j)%10086001;
		}
	}

輸入格式

輸入資料只有一行 , , ,包含一個正整數 n n n

輸出格式

輸出資料只有一行 , , ,表示所求答案 m o d 10086001 mod10086001 mod10086001的值

樣例

樣例輸入1

10

樣例輸出1

122

樣例輸入2

1000

樣例輸出2

2475190

資料范圍與提示

對于所有的資料
0 < n < 5 ? 1 0 6 + 1 0<n<5*10^6+1 0<n<5?106+1

題解

不知道歐拉函式的點這里
先把這個問題分解成多個:

	for(int i=1;i<=n;i++){
		ans+=__gcd(n,i);
	}

這個問題就可以用以下演算法求解
n n n與小于他的數的最大公約數一定是這個數的約數,然后列舉這個數的約數 m m m,尋找這個約數與那些小于 n n n的數中與 n n n的最大公約數和這個約數相同的個數,就可以使用歐拉函式,而個數就與 n / m n/m n/m的歐拉函式相等,因為與他互質的數乘這個約數 m m m與 n n n不可能有更大的公約數,所以以上問題可以用以下代碼實作：

void g(long long n){//求歐拉函式
	phi[1]=1;
    for(long long i=2;i<=n;i++){
        if (!m[i]){
            p[++u]=i;
            phi[i]=i-1;   
        }    
        for (long long j=1;j<=u&&p[j]*i<=n;j++){
            m[p[j]*i]=1;
            if(i%p[j]==0){
                phi[p[j]*i]=phi[i]*p[j];
                break;
            }
            else phi[p[j]*i]=phi[i]*(p[j]-1);
        }
    }
}
long long h(long long n){//計算以上問題
	ans=0;
	cnt=0;
	for(long long i=1;i*i<=n;i++){
		if(n%i==0){
			r[++cnt]=i;
			if(i!=n/i)r[++cnt]=n/i;
		}
	}
	for(long long i=1;i<=cnt;i++){
		ans+=phi[n/r[i]]*r[i];
	}
	return ans;
}

如果用上面的方法列舉每個 n n n會超時
然而在這道題中可以得到簡化
直接列舉1-n的數的倍數,每個倍數都是上述問題的“n”
所以直接加給 a n s ans ans就行了

#include<bits/stdc++.h>
using namespace std;
int n,a[5000005],ans;
int cnt=0,phi[5000005]={},p[5000005]={};
bitset<5000005>f;
void g(int x){
	phi[1]=1;
	for(int i=2;i<=x;i++){
		if(!f[i]){
			p[++cnt]=i;
			phi[i]=i-1;   
		}
		for (int j=1;j<=cnt&&p[j]*i<=x;j++){
			f[p[j]*i]=1;
			if(i%p[j]==0){
				phi[p[j]*i]=phi[i]*p[j];
				break;
			}
			else phi[p[j]*i]=phi[i]*(p[j]-1);
		}
	}
}
int main(){
	long long ans2=0;
	scanf("%d",&n);
	g(n);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
			ans2+=1LL*phi[j/i]*i;
			ans2%=10086001;
		}
	}
	printf("%lld\n",ans2);
	return 0;
}

LJS的GCD (加強版)

題目描述

L J S LJS LJS來到了一間密室里
L J S LJS LJS為了快點與同伴們會合準備用勉強還能運行的計算機計算足夠大的 g c d gcd gcd和因為他知道只有這樣他才能用強大的資料來沖擊這件密室的門
求

	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			ans+=__gcd(i,j)%10086001;
		}
	}

但這只是杯水車薪， L J S LJS LJS決定用 t t t組資料同時沖擊密室門，

輸入格式

本題有多組輸入，
第一行輸入一個整數 t t t,表示有 t t t組資料，
接下來 t t t行，每行一個整數 n n n，

輸出格式

對于每一個 n n n，輸出上式的結果

樣例

樣例輸入

2
10
1000

樣例輸出

122
2475190

題解

對于這道題，因為上面的 j j j都是第一個問題的 n n n，所以就多開一個陣列存每個問題的答案，再求前綴和，

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005];
int cnt,phi[1000005],p[1000005];
long long ans[1000005];
bitset<1000005>f;
void g(int x){
	phi[1]=1;
	for(int i=2;i<=x;i++){
		if(!f[i]){
			p[++cnt]=i;
			phi[i]=i-1;   
		}
		for (int j=1;j<=cnt&&p[j]*i<=x;j++){
			f[p[j]*i]=1;
			if(i%p[j]==0){
				phi[p[j]*i]=phi[i]*p[j];
				break;
			}
			else phi[p[j]*i]=phi[i]*(p[j]-1);
		}
	}
}
int main(){
	long long ans2=0,a,T;
	n=1000000;
	g(n);
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j+=i){
			ans[j]+=1LL*phi[j/i]*i;
			ans[j]%=10086001;
		}
	}
	for(int i=1;i<=n;i++){
		ans[i]+=ans[i-1];
		ans[i]%=10086001;
	}
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&a);
		printf("%lld\n",ans[a]);
	}
	return 0;
}