【欧拉函数||容斥】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乘上C 2 \choose num(d),其中num(d)指的是d出现的次数。因为任意两个数才有公约数,从有d这个公因数的所有数中选择两个即可。

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

代码见 题解 F

2.欧拉函数

首先欧拉函数有个性质:n = \sum\limits_{d|n}φ(d)也就是说n的所有因数的欧拉函数之和等于n本身。

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

n*C 2 \choose num(n)

其中2 \choose num(n可以看作是0..num(n)-1的等差求和公式:0+1+2+..+num(n)-1。n则可以写为\sum\limits_{d|n}φ(d)

(0+1+2+..+num(n)-1) * \sum\limits_{d|n}φ(d)

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

那每加入一个数x。可以把答案加上num(k) * \sum\limits_{k|x}φ(k)

#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++) phi[i]=0;
    phi[1]=1;
    for(ll i=2;i<=maxn;i++) 
        if(!phi[i])
        {
            for(ll j=i;j<=maxn;j+=i)
            {
                if(!phi[j]) 
Read the rest

【矩阵快速幂-构造】I – Algebraic Problem LightOJ – 1070

Given the value of a+b and ab you will have to find the value of an+bn. a and b not necessarily have to be real numbers.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. Each number in the input file fits in a signed 32-bit integer. There will be 
Read the rest

【组合数求模】K – Combinations LightOJ – 1067

Given n different objects, you want to take k of them. How many ways to can do it?

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.

Take 1, 2

Take 1, 3

Take 1, 4

Take 2, 3

Take 2, 4

Take 3, 4

Input
Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 
Read the rest

【组合数学】J – Rooks LightOJ – 1005

A rook is a piece used in the game of chess which is played on a board of square grids. A rook can only move vertically or horizontally from its current position and two rooks attack each other if one is on the path of the other. In the following figure, the dark squares represent the reachable locations for rook R1 from its current position. The figure also shows that the rook R1 and R2 are in attacking positions where 
Read the rest

【long long 坑】‘早自习打卡’

Description
重庆游戏与电子竞技大学开始使用电子打卡机进行早自习考勤,打卡机记录了每个人到达教室和离开教室的时间。现在辅导员想知道今天有多少同学在7:20之前(包括7:20)到达,7:40之后(包括7:40)离开,且这段时间内没有离开过教室的同学有多少,但是考勤记录被打乱了,于是他把这个任务交给了你。
Input
每个输入包含一个测试用例。 每个测试用例由多行记录组成,每行记录由时间(以h:m的形式,h(1<=h<=24)表示小时,m(0<=m<60)表示分钟)和学号s(s由十位数字组成)组成。 输入保证记录由合法的记录打乱得到,即同一个人时间轴上第一次记录一定是到达记录,相邻两次记录一定是一次到达一次离开。 记录最多有100000行。
Output
输出一个整数,表示在7:20之前(包括7:20)到达,7:40之后(包括7:40)离开,且这段时间内没有离开过教室的同学的数量。
Sample Input
7:19 2015233333
7:40 2015666666
7:20 2015666666
7:39 2015233333
7:00 2015123456
Sample Output
1

把学号离散化,但学号已经超过了1e10,所以要用long long

#include<bits/stdc++.h>
#include<queue>
#include<map>
#include<string>
#include<cstring>
using namespace std;
typedef long long ll;
map<ll, int> id;
priority_queue<int,vector<int> ,greater<int > > tl[100010];
int ans=0,cnt=0;
int main()
{
	int h,m;
	ll s;
	while(scanf("%d:%d %lld",&h,&m,&s)!=EOF)
	{
		if(id.count(s)==0)
		{
			id[s]=++cnt;
		}
		tl[id[s]].push(h*100+m);
	}
	int a,b;
	for(int i=1;i<=cnt;i++)
	{
		int card=tl[i].size();
		while(card>1)
		{
			a=tl[i].top();tl[i].pop();
			b=tl[i].top();tl[i].pop();
			card-=2;
			if(a<=720&&b>=740)
			{
				ans++;
				break;
			
Read the rest

【最大匹配】‘组队难题’

Description
一年一度的保研杯又开始了,重庆游戏与电子竞技大学的同学们都跃跃欲试。今年学校收集了参赛学生的信息,打算统一分配队伍。学校把学生分为端茶、倒水和大佬三种类型,一个队伍由三个学生组成,而且不能同时有多个端茶学生或者多个倒水学生。大佬比较佛系,不会和其他学生起冲突,但是剩下两种学生都是凡人,所以一些学生之间会有矛盾。现在问题来了,在避免矛盾的前提下,最多能组成多少只队伍呢?
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个整数,学生数量N(1<=N<=300)和矛盾数量M(0<=M<=90000)。学生的编号从1到N。 接下来的N行,每行包括一个字符串,第i行的字符串表示i号学生的类型:”DL”表示大佬,”DC”表示端茶,”DS”表示倒水。 接下来的M行,每行包括两个正整数,表示有矛盾的学生的编号。保证矛盾双方编号不同。 数据保证矛盾不会和”DL”类型的同学有关,保证每对同学的矛盾最多只会出现一次。
Output
输出一个整数,表示最多能组成的队伍数量。
Sample Input
4 2
DL
DC
DC
DS
2 4
3 4
Sample Output

虽然一眼就看出来是最大匹配,但是有个坑点没有注意到。

一个队不能有多个端茶送水但是可以有多个大佬…………………………

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int dl=0;
int d[303]={0};
vector<int> qds,qdc;
int cp[303][303]={0};
int vis[303]={0};
int mch[303]={0};
int fbfs(int x)
{
	int j;
	for(int k=0;k<qdc.size();k++)
	{
		j=qdc[k];
		if(cp[x][j]==1 && vis[j]==0)
		{
			vis[j]=1;
			if(mch[j]==0 || fbfs(mch[j]))
			{
				mch[j]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		char 
Read the rest

【数位DP-技巧】长度为N的数串每M个和都为质数

Description
经过不懈的努力,你在后山挖出了一个宝箱,旁边还有一张纸条,上面写着两个数字还有一段话:“我是九头龙晗源,想要我的资源吗?如果想要的话,那就到oj.cqupt.edu.cn.cqu.pt去找吧,我全部都放在那里。密码是满足由N位数字组成,且每连续M个数字之和都是质数的数字串的个数。N和M我写在纸上了。”
Input
每个输入包含一个测试用例。 每个测试用例包括两个整数N(1<=N<=12)和M(1<=M<=4)。
Output
输出一个整数,表示密码,即满足由N位数字组成,且每连续M个数字之和都是质数的数字串的个数。 这N位数字每一位可以是0~9,数字串可以有前导0。
Sample Input
2 2
Sample Output
37
HINT
当M>N时,密码为0

无脑滚表虽然过了,但和MZJJ学到了很多数位dp的技巧。

比如如何取位,如何快速加和一个3位数,如何巧妙的避开判断m的大小。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,md;
int pri[55];
int g[10001];
ll dp[55][5555];
void init()
{
	for(int i=1;i<=49;i++) pri[i]=1;
	pri[0]=0;pri[1]=0;
	for(int i=2;i<=7;i++)
	{
		if(pri[i])
		{
			for(int j=i*i;j<=49;j+=i) pri[j]=0;
		}
	}
	for(int i=1;i<=9999;i++) g[i]=g[i/10]+i%10;
}
ll dfs(int pos,int num)
{
	if(pos==0) return 1;
	ll &ans=dp[pos][num];
	if(~ans) return ans;
	ans=0;
	for(int i=0;i<=9;i++)
	{
		if(pos+m-1>n||pri[g[num]+i]==1)
		{
			ans+=dfs(pos-1,(num*10+i)%md);
		}
	}
	return ans;
Read the rest

【高斯消元解异或方程组】开关问题


1518: 熄灯的工作
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 471  Solved: 19
[Submit][Status][Web Board]
Description
重庆游戏与电子竞技大学的熄灯时间是11点半。每天晚上,宿管嬢嬢都是用总开关来关灯的。但是今天总开关坏了,只有一些分开关,每个开关控制一些灯,灯都有可能被多个开关控制。按一次开关,所有它所控制的灯都会切换一次状态,即亮的灯变灭,灭的灯变亮。一开始所有灯都是亮的,宿管嬢嬢想把所有的灯都灭了,但是她面对一堆开关头皮发麻,只好找来了头铁的你来解决这个问题。
Input
每个输入包含一个测试用例。 每个测试的第一行包括两个正整数,表示灯的数量N(1<=N<=100)和开关的数量M(1<=M<=100)。灯的编号从1到N。 接下来M行,每行的开头是一个整数,表示这个开关控制的灯的数量X(0<=X<=N),接下来是X个不相同的数字,表示这个开关控制的灯的编号。
Output
如果可以用这些开关关掉所有灯,输出”YES”。否则,输出”NO”。
Sample Input
3 2
2 1 2
2 1 3
Sample Output
NO

学了一下高斯消元,异或方程还挺有意思的

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[202][202]={0};
void gauss()
{
	for(int i=1;i<=n;i++)
	{
		int j=i;
		while(j<=n&&!a[j][i]) j++;
		if(j>n) continue;
		if(i!=j) for(int k=1;k<=m+1;k++) swap(a[i][k],a[j][k]);
		for(int l=1;l<=n;l++)
			if(l!=i&&a[l][i])
				for(int k=1;k<=m+1;k++) a[l][k]^=a[i][k];
	}
}
int main()
{
	int ans=1;
	scanf("%d%d",&n,&m);
	//a[n][m];
	for(int i=1;i<=n;i++) a[i][m+1]=1;
	
Read the rest

LightOJ – 1282 求取数字前三位和后三位

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

Output
For each case, print the case number and the three leading digits (most significant) and three trailing 
Read the rest

LightOJ – 1138 Trailing Zeroes (III)

You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains an integer Q (1 ≤ Q ≤ 108) in a line.

Output
For each case, print the case number and N. If 
Read the rest