【欧拉函数||容斥】gcd之和

Description
给出一个数列,求数列中任意一对数的最大公因数之和。
最大公因数的定义可以查看 baike.baidu.com/item/最大公因数 

Input
 多组数据。
输入的第一行包括一个整数表示数据组数T(1<=T<=10)。
每组数据的第一行包括一个整数表示数列的长度N(1<=N<=10000)。
第二行包括N个整数,第i个整数表示数列的第i个数ai(1<=ai<=10000)。

Output
每组数据在单独的一行中输出数列中任意一对数的最大公因数之和。 

Sample Input
3
3
2 1 3
4
4 3 9 6
7
7 7 7 7 7 7 7
Sample Output
3
13
147
HINT
 对于第一组数据:


gcd(2,1)+gcd(2,3)+gcd(1,3)=1+1+1=3

对于第二组数据:

gcd(4,3)+gcd(4,9)+gcd(4,6)+gcd(3,9)+gcd(3,6)+gcd(9,6)=1+1+2+3+3+3=13

对于第三组数据:

gcd(7,7)*(6+5+4+3+2+1)=7*21=147 

关于这题有很多种解法。

1.容斥

假设d为N公因数,那么公因数之和就是所有的d乘上,其中num(d)指的是d出现的次数。因为任意两个数才有公约数,从有d这个公因数的所有数中选择两个即可。

然而这下算出来的是所有公因数的和,我们需要的是最大公因数的和。所以要除重,可以利用容斥原理。d算出的答案减去d的倍数算出的答案即为最大公约数之和。例如最大公因数为2的,就可以算出公因数为2的,再减去公因数和为4,8,16…的。倒过来容斥就可以了。

代码见 题解 F

2.欧拉函数

首先欧拉函数有个性质:也就是说n的所有因数的欧拉函数之和等于n本身。

假设,则x,y小于n的公约数一定是相同的。可以得到:任意两数的gcd等于他们的公因数的欧拉函数值之和。则同样有某个gcd的和为

其中可以看作是0..num(n)-1的等差求和公式: 。n则可以写为

$$

可以看出每个公因数的Φ值乘上自己出现的次数都会对gcd的和做出一定贡献。而且因为每个d都有对应的gcd,所以不存在重复的情况。

那每加入一个数x。可以把答案加上

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e5+233;
ll phi[maxn+23]={0};
ll a[maxn+23];
vector<ll> d[maxn+23];
void phi_t()
{
	for(ll i=2;i<=maxn;i++) 
Read the rest

线性同余方程组的合并

类似于

$$a_ix\equiv b_i\mod m_i$$

的方程组就是线性同余方程组
根据同余的可加性,可令

$$x\equiv B \mod lcm(m_i) $$

所以答案就转化为了求B和lcm

$$a_1x \equiv b_1 \mod m1$$

$$x\equiv (b_1/\gcd(a_1,m_1))*(a_1^{-1}/gcd(a_1,m_1)) \mod (m_1/gcd(a_1,m_1))$$

$$x \equiv B_1 \mod m1$$

$$x=B_1+m_1*t $$此时的m1*t是未知的

带入第二个方程,并整理

$$a(B_1+m_1t) \equiv b_2 \mod m_2$$

$$am_1t \equiv b_2-aB_1 \mod m_2$$

解出t

$$t \equiv (b_2-aB_1)/gcd(am_1,m_2) * (am_1)^{-1}/gcd(am_1,m_2) \mod (m_2)/gcd(am_1,m_2)$$

把t带入

$$x=B_1+m_1*t $$

$$x\equiv B_2 \mod lcm(m_1,m_2) $$

$$x=B_2+lcm*t$$

再带入第三个方程即可向下合并

//返回一个b,m对 
pair<int, int> inner_congruence(const vector<int> &A,const vector<int> &B,const vector<int> &M)
{
	int x=0,m=1;
	for(int i-9;i<A.size();i++)
	{
		int a=A[i]*m,b=B[i]-A[i]*x,d=gcd(a,M[i]);
		if(b%d!=0) return make_pair(0,-1); //无解
		
Read the rest

【离线并查集】问题集合

  • 有 N 个数,初始均为 0。有 Q 个操作,第 i 个操作会把第 Li 到第 Ri 个数改为 Ci。问,所有操作结束后,每个数的值

并查集维护每个点右边最近的未修改的点,把操作全部读入以后倒序处理,因为是倒着处理所以每个点只能被修改一次,直接用数组记录就可以了。初始f[i]=i;当l..r合并以后区间内每个f[i]=i+1;查询函数加上路径压缩,当遇见一个被改变过的点可以立刻跳过后面所有被改变了的点

#include<iostream>
#include<stdio.h>
using namespace std;
int f[1001]={0};
int qm[1001][3]={0};
int a[1001]={0};
int n=0,q=0;
int ff(int x)
{
	if(f[x]==x) return x;
	else return f[x]=ff(f[x]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n+2;i++) f[i]=i;
	for(int i=q;i>0;i--)
	{
		scanf("%d%d%d",&qm[i][1],&qm[i][2],&qm[i][0]);
	}
	for(int i=1;i<=q;i++)
	{
		int l=qm[i][1],r=qm[i][2],v=qm[i][0];
		while(l<=r)
		{			
			l=ff(l);
			if(l<=r)
			{
				a[l]=v;
				f[l]=l+1;
				l+=1;
			}
			else
			{
				break;
			}
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
} 

 … Read the rest

【数学-贪心-末状态已知】问题集合

  • 蓝书 P4 分金币

https://vjudge.net/problem/UVA-11300

关于本题的“想一想为什么”:因为非齐次方程组的系数行列式为0,所以方程的解不唯一,所以最后一个方程没有贡献。

末态相同的题目,可以往方程组方向去想。最后可以往坐标的距离方面去靠。

  • 蓝书 P7 雕塑

本题第一个设想“有一个雕塑不会动”的证明:

设开始每个墓碑相差A,移动后每个墓碑相差M,M可以不相同,因为有加进来的雕塑。设Xi为向下一个雕塑移动的距离。则有

$$A-X_1+X_2=M =>X_2=X_1-(A-M)$$

$$A-X_2+X_3=M =>X_3=X_1-2(A-M)$$

$$…$$

$$A-X_n+X_1=M =>X_n=X_1-n(A-M)$$

 

同样可以变成X1到各个数字的距离最小的问题,即可知道X1在中位数的时候此时的距离为0。所以必然有一个雕塑它移动的距离为0。但不可用此方法求解答案,因为M仅仅是假设存在一个M使其满足末态,由于加入的雕塑不知道位置所以M无法确定。应采用贪心的方法求解… Read the rest

【优先队列-贪心】问题集合

  • 中间商优化

http://codeforces.com/problemset/problem/867/E

一个长度为N的序列,代表每天股票的价格,每天只能执行 买/卖/无动作 三种操作。问如何才能赚得最多。

维护一个优先队列,队首存当前最小的价格,见到比最小的价格高的就先卖掉,并且把低价股票的价格变成当前价格,更低的就进队。如果以后遇到更高的可以和交易过的股票交易,也可以和没交易过的股票交易,它们赚的钱是一样的。。经过xyjj的指点知道了这类题的做法叫中间商优化,先找到更高的卖了提升价格,以后可以继续交易。

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector> 
#include<utility>
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > b;

ll n,t;
ll ans=0;
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&t);
		b.push(t);
		if(b.top()<t)
		{
			ans+=t-b.top();
			b.pop();
			b.push(t);
		}
	}
	printf("%lld",ans);
}

 … Read the rest