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

Description

Input
多组数据。

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.容斥

2.欧拉函数

n*C 2 \choose num(n)

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

#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]) 

## 【矩阵快速幂-构造】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 

## 【组合数求模】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 

## 【组合数学】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 

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

Description

Input

Output

Sample Input
7:19 2015233333
7:40 2015666666
7:20 2015666666
7:39 2015233333
7:00 2015123456
Sample Output
1

#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;


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

Description

Input

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 

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

Description

Input

Output

Sample Input
2 2
Sample Output
37
HINT

#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;


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


1518: 熄灯的工作
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 471  Solved: 19
[Submit][Status][Web Board]
Description

Input

Output

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;


## 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 
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.
For each case, print the case number and N. If