• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

LJS的GCD

互联网 diligentman 2天前 7次浏览

题目描述

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("%lldn",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("%lldn",ans[a]);
	}
	return 0;
}


程序员灯塔
转载请注明原文链接:https://www.wangt.cc/2020/10/ljs%e7%9a%84gcd/
喜欢 (0)