首页 > 其他分享 >P2398 GCD SUM——欧拉函数

P2398 GCD SUM——欧拉函数

时间:2023-01-01 00:33:41浏览次数:59  
标签:phi ch GCD int SUM P2398 maxn ll define

image

此题可以拓展为 \(\sum\limits^n_{i=1}\sum\limits^m_{j=1}\gcd(i,j)\)

结论是 \(\sum\limits^{\min(n,m)}_{d=1}\varphi(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{d}\rfloor\)

#include <bits/stdc++.h>
#define rei register int
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, ll mod){long long res = 1;  while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod;  b >>= 1;  }  return res;}

using namespace std;
const int maxn = 100000;
ll p[maxn], vis[maxn], cnt;
ll phi[maxn];
void get_phi(int n)
{
	phi[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) {
			p[cnt++] = i;
			phi[i] = i - 1; // phi(p) = p -1
		}
		for (int j = 0; i * p[j] <= n; j++) {
			int m = i * p[j];
			vis[m] = 1;
			if (i % p[j] == 0) {
				phi[m] = p[j] * phi[i];
				break;
			}
			else {
				phi[m] = (p[j] - 1) * phi[i];
			}
		}
	}
}
int main()
{
	int n;
	cin >> n;
	get_phi(maxn);
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int t = n / i;
		ans += phi[i] * t*t;
	}
	cout << ans << endl;
    return 0;
}

标签:phi,ch,GCD,int,SUM,P2398,maxn,ll,define
From: https://www.cnblogs.com/CYLSY/p/17017651.html

相关文章

  • Sumitomo Mitsui Trust Bank Programming Contest 2019 —— B
    也不知道这比赛为啥要取这么长的名称(传送门:https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_e哈哈,你被骗了!但网址是真的!题意有红绿蓝三种帽子RedandBl......
  • Trick 5: 关于 GCD 的一些处理方法和性质
    经典的mobius:\(\varepsilon(x)=\sum\limits_{d|x}\mu(d)\)经典的euler:\(x=\sum\limits_{d|x}\varphi(d)\)处理区间问题。如果考虑一段区间的\(\gcd\),那......
  • 模拟spring-kafka实现kafka的consumer监听
    背景:因为某些原因,无法直接使用springboot提供的@KafkaListener,改为模拟springboot注解的方式搬过来实现首先创建一个业务处理的service,这个service主要用于消费下来的消息......
  • 容斥原理与gcd的问题
    gcd个数的处理(i,j无限制)P2398GCDSUMi为1-n,j为1-m,求gcd为k的个数代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintM=1e5+5;......
  • AtCoder-abc230_g GCD Permutation 容斥
    J-GCDPermutation传送门:J-GCDPermutation知识点:素数筛、容斥定理、gcd题意:长度为n的一个排列a中,求满足\(gcd(i,j)!=1且gcd(a_i,a_j)!=1\)的i,j对数。i,j可以......
  • cesaro sum和tauber型定理
    缓更Definition.1:Givenasequence\(\{a_n\}(n\ge1)\),thecesarosumofadenote$\lim_{n\rightarrow\infty}\frac{\sum_{i=1}^na_i}{n}$,ifthislimit......
  • 404. Sum of Left Leaves
    Giventherootofabinarytree,returnthesumofallleftleaves.Aleafisanodewithnochildren.Aleftleafisaleafthatistheleftchildofanother......
  • Atcoder Beginner Contest ABC 283 Ex Popcount Sum 题解 (类欧几里得算法)
    题目链接令\(p=\lfloor\frac{n-r}m\rfloor\),则我们其实是要对所有\(0\lei\le29\)求\(\sum_{j=0}^p(\lfloor\frac{mj+r}{2^i}\rfloormod\2)\)。右边那个东西如果没......
  • Pytest插件pytest-assume多重断言
    Pytest插件pytest-assume多重断言背景importpytestdeftest_assume1():assert1==2print('hello')assert2==3if__name__=='__main__':......
  • Data & Cloud Summit 2021 活动小记
    前言        大家好,我是梦想家。前段时间我写了一篇文章,​​《参加七牛云“PISA”发布会随想录》​​,当时在评论区说到,如果点赞过15,7月30日将在上海浦东香格里拉......