LJS的GCD

10/19 08:29
阅读数 15

题目描述

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<5106+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;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部