首页 > 其他分享 >CF1900D Small GCD 题解

CF1900D Small GCD 题解

时间:2023-12-19 11:55:55浏览次数:38  
标签:gcd int 题解 times 枚举 MAXN Small CF1900D

原题链接:CF1900D,题意不多赘述。

首先可以将 \(a\) 数组排序,并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演,但是也可以不用,因为我不会。

假设我们当前已经枚举到了 \(a_i\),设 \(f_k\) 表示 \(a_1\) 到 \(a_{i-1}\) 中是 \(k\) 的倍数的数有多少个,\(g_k\) 表示 \(a_{1}\) 到 \(a_{i-1}\) 中满足 \(\gcd(a_j,a_i)=k\) 的数有多少个。\(f_k\) 可以直接通过枚举每一个数的所有因子算出,\(g_k\) 可以考虑用容斥算出。具体的,首先将 \(g_k\) 赋值为 \(f_k\),但是我们会发现有一些数不满足条件。比如 \(4\) 和 \(8\) 都是 \(2\) 的倍数,但是 \(\gcd(4,8) \ne 2\),所以我们直接将每一个 \(g_k\) 都减去 \(g_x(k \mid x,x \mid a_i)\) 即可。对于每一个 \(a_i\),最终答案为 \(\sum g_j\times j \times (n-i)\)。

可以先预处理出 \(1\) 到 \(100000\) 的所有因数,小常数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
int t,n,a[MAXN],f[MAXN],g[MAXN]; 
vector <int> v[MAXN];
signed main()
{
	for(int i = 1e5;i >= 1;i--)
		for(int j = i;j <= 1e5;j += i) v[j].emplace_back(i);
	cin >> t;
	while(t--)
	{
		memset(f,0,sizeof f),memset(g,0,sizeof g);
		cin >> n;
		for(int i = 1;i <= n;i++) cin >> a[i];
		sort(a + 1,a + n + 1);
		int ans = 0;
		for(int i = 1;i <= n;i++)
		{
			for(auto j : v[a[i]]) g[j] = f[j],f[j]++;
			for(auto j : v[a[i]])
				for(auto k : v[j]) if(k != j) g[k] -= g[j];
			for(auto j : v[a[i]]) ans += (g[j] * (n - i) * j);
		}
		cout << ans << endl;
	}
	return 0;
}

标签:gcd,int,题解,times,枚举,MAXN,Small,CF1900D
From: https://www.cnblogs.com/Creeperl/p/17913380.html

相关文章

  • CF1902D Robot Queries 题解
    题意:有一个二维平面直角坐标系,给定一串向某个方向移动\(1\)个单位的操作。有\(q\)个询问,对于每个询问给定\(x,y,l,r\),问如果倒着做\(l\)到\(r\)这段区间中的操作,是否会经过\((x,y)\)。ds题。先预处理出\(sx_i,sy_i\)表示执行完操作\(i\)后的位置,如果在\([l,r]\)......
  • 华中师范大学2023新生赛 H 龙 题解
    Link华中师范大学2023新生赛H龙Question有\(m\)个宝石孔,有\(n\)个宝石,每个宝石可以提升\(a_i\)点战斗力每次镶嵌一个宝石,被选中的宝石会随机选择一个宝石孔进去,如果这个孔原来有宝石,则原来的宝石会被损坏你可以任意决定镶嵌宝石的顺序,她想知道,如果把着\(n\)颗宝......
  • 华中师范大学2023新生赛 D 身无彩凤双飞翼 题解
    Link华中师范大学2023新生赛D身无彩凤双飞翼Question给出一个\(n\timesm\)的网格,网格上有一些障碍,问最少添加多少障碍才能使\((1,1)\)和\((n,m)\)不连通Solution我好像用了一种和标答不一样的写法我们先对图bfs一次,如果\((1,1)\)不能到达\((n,m)\),则图本来就......
  • CF1905 B Begginer's Zelda 题解
    LinkCF1905BBegginer'sZeldaQuestion给出一棵树,每次能把一条路径压缩成一个点,求最少几次把树压缩成一个点Solution贪心的想,路径肯定越长越好,所以肯定是以一个儿子节点为起点,以一个儿子节点为终点,儿子节点合并了儿子到根的父节点也合并了,每次合并两个儿子节点,假设儿子节点......
  • 【题解】CodeForces-1913
    CodeForces-1913ARatingIncrease依题意模拟。提交记录:Submission-CodeForcesCodeForces-1913BSwapandDelete交换免费就是能任意重排,从头开始尽量填相反的,剩下只能删去了。提交记录:Submission-CodeForcesCodeForces-1913CGamewithMultiset从大到小能减则减一定......
  • 【题解】CodeForces-1905
    CodeForces-1905AConstructiveProblems发现沿着对角线放就行了,答案是\(\max(n+m)\)。提交记录:Submission-CodeForcesCodeForces-1905BBegginer'sZelda最优操作每次删两个叶子(除了最后一次只剩两个节点),所以答案是叶子个数除以二上取整。提交记录:Submission-CodeForc......
  • Java面向对象程序设计(上海交通大学出版社)12章及以后的课后问题解析
    1)Map集合和Collection集合的区别是什么? Map集合和Collection集合都是Java集合框架中的接口,它们之间有一些关键的区别:元素存储方式:Collection:用于存储单一元素的集合接口。它继承自Iterable接口,包含常见的子接口如List、Set。Map:用于存储键值对(key-value......
  • Cesium开发遇到的问题解决
    问题1:后台缓存收回进程无法释放上下文[/BUSINESS的缓存的[10]%-请考虑增加缓存的最大大小。原因:出现该问题是Tomcat启动时,占用的缓存较大,Tomcat默认的缓存是10000KB.解决:需要调整Tomcat目录下\conf\context.xml文件中的缓存的最大值,需要添加在<Context></Context>标签内,添加项如......
  • 题解 LGP7294【[USACO21JAN] Minimum Cost Paths P】/ accoders::NOI 5696【棋子】
    problemFarmerJohn的牧草地可以看作是一个\(N×M\)(\(2≤N≤10^9,2≤M≤2⋅10^5\))的正方形方格组成的二维方阵(想象一个巨大的棋盘)。对于\(x∈[1,N],y∈[1,M]\),从上往下第\(x\)行、从左往右第\(y\)列的方格记为\((x,y)\)。此外,对于每一个\(y∈[1,M]\),第\(y\)列拥有一个......
  • JOISC2020题解
    \(\text{ByDaiRuiChen007}\)ContestLinkA.Building4ProblemLink题目大意给\(2n\)个数对\((a_i,b_i)\),构造一个非降序列\(c_i\)满足\(\forall1\lei\len,c_i\in\{a_i,b_i\}\),且\(c_i=a_i\)的位置恰好有\(n\)个。数据范围:\(n\le5\times10^5\)。思路......