关于欧拉函数一个重要性质，找到一个简洁的证明，如下（from StackExchange)

对于这个性质，简单来说就是对于每个$n$的约数，他们的欧拉函数之和为$n$本身，在化简计算表达式的时候经常起到作用。

[SHOI2001]击鼓传花

题目描述

HC(Happy Child )小朋友最近经常在教室里跟同学一起玩击鼓传花的游戏，规则是第n个拿到花的小朋友必须说出n!最后一位非0 的数字，如此循环游戏，如果谁讲错了就得罚唱一支歌曲。

经过几次游戏，HC小朋友认为只要把前一个小朋友说得数字去乘以n，说出得到的数的最后一位非0的数字就可以了，可惜HC小朋友这次轮到了第15个，结果被罚了唱歌(应该是8，但是HC小朋友却说了3)。

HC小朋友不希望这样的事情再次发生，所以希望你能编写一个程序，能够计算出n!的最后一位非0的数字。

输入输出格式

输入格式：

输入有5行，第I(1≤i≤5)行是一个n(1≤n≤10100，10的100次幂)。

输出格式：

输出有5行。

第I行对应输入中第I行的n的阶乘的最后一位非0的数字。

输入输出样例

输入样例#1：

输出样例#1：

题解

让你求一个大数阶乘的最右非0数。

考虑到有2有5两个质因子就会有一个0出现！

如果学过扩展Lucas的话应该知道如何快速计算阶乘的某一个质因子个数。

这时候剩余一些2和其他的数。

考虑怎么计算他们对10取余的答案。

循环节！

这是显而易见的，在去掉那些配对的2和5之后把阶乘数列写出来（在对10取余并且去掉了2和5，多去掉的2可以后面快速幂直接算），若干项就会有循环，具体大概是鸽巢原理的证明。

本题做完了，~~我当场爆切~~

4382: [POI2015]Podział naszyjnika

Description

长度为n的一串项链，每颗珠子是k种颜色之一。第i颗与第i-1,i+1颗珠子相邻，第n颗与第1颗也相邻。
切两刀，把项链断成两条链。要求每种颜色的珠子只能出现在其中一条链中。
求方案数量（保证至少存在一种），以及切成的两段长度之差绝对值的最小值。

Input

第一行n,k(2<=k<=n<=1000000)。颜色从1到k标号。
接下来n个数，按顺序表示每颗珠子的颜色。（保证k种颜色各出现至少一次）。

Output

一行两个整数：方案数量，和长度差的最小值

Sample Input

9 5
2 5 3 2 2 4 1 1 3

Sample Output

4 3

HINT

四种方法中较短的一条分别是(5),(4),(1,1),(4,1,1)。相差最小值6-3=3。

题解

3237: [Ahoi2013]连通图

题解

3534: [Sdoi2014]重建

Description

T国有N个城市，用若干双向道路连接。一对城市之间至多存在一条道路。
在一次洪水之后，一些道路受损无法通行。虽然已经有人开始调查道路的损毁情况，但直到现在几乎没有消息传回。
辛运的是，此前T国政府调查过每条道路的强度，现在他们希望只利用这些信息估计灾情。具体地，给定每条道路在洪水后仍能通行的概率，请计算仍能通行的道路恰有N-1条，且能联通所有城市的概率。

Input

输入的第一行包含整数N。
接下来N行，每行N个实数，第i+l行，列的数G[i][j]表示城市i与j之
间仍有道路联通的概率。
输入保证G[i][j]=G[j][i]，且G[i][j]=0；G[i][j]至多包含两位小数。

Output

输出一个任意位数的实数表示答案。
你的答案与标准答案相对误差不超过10^(-4)即视为正确。

Sample Input

Sample Output

0.375

HINT

1 < N < =50

题解

4144: [AMPPZ2014]Petrol

Description

给定一个n个点、m条边的带权无向图，其中有s个点是加油站。

每辆车都有一个油量上限b，即每次行走距离不能超过b，但在加油站可以补满。

q次询问，每次给出x,y,b，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。

Input

第一行包含三个正整数n,s,m(2<=s<=n<=200000,1<=m<=200000)，表示点数、加油站数和边数。

第二行包含s个互不相同的正整数c[1],c[2],…cs，表示每个加油站。

接下来m行，每行三个正整数u[i],v[i],di，表示u[i]和v[i]之间有一条长度为d[i]的双向边。

接下来一行包含一个正整数q(1<=q<=200000)，表示询问数。

接下来q行，每行包含三个正整数x[i],y[i],bi，表示一个询问。

Output

输出q行。第i行输出第i个询问的答案，如果可行，则输出TAK，否则输出NIE。

Sample Input

6 4 5
1 5 2 6
1 3 1
2 3 2
3 4 3
4 5 5
6 4 5
4
1 2 4
2 6 9
1 5 9
6 5 8

Sample Output

TAK
TAK
TAK
NIE

HINT

题解

4400: tjoi2012 桥

Description

有n个岛屿，m座桥，每座桥连通两座岛屿，桥上会有一些敌人，玩家只有消灭了桥上的敌人才能通过，与此同时桥上的敌人会对玩家造成一定伤害。而且会有一个大Boss镇守一座桥，以玩家目前的能力，是不可能通过的。而Boss是邪恶的，Boss会镇守某一座使得玩家受到最多的伤害才能从岛屿1到达岛屿n(当然玩家会选择伤害最小的路径)。问，Boss可能镇守桥有哪些。

Input

第一行两个整数n,m
接下来m行，每行三个整数s,t,c，表示一座连接岛屿s和t的桥上的敌人会对玩家造成c的伤害。

Output

一行，两个整数d,cnt，d表示有Boss的情况下，玩家要受到的伤害，cnt表示Boss有可能镇守的桥的数目。

Sample Input

3 4
1 2 1
1 2 2
2 3 1
2 3 1

Sample Output

3 1

HINT

100%的数据，1<=n<=100000，1<=m<=200000，1<=c<=10000，数据保证玩家可以从岛屿1到达岛屿n

题解

2612: [Poi2003]Sums

Description

我们给定一个整数集合A. 考虑一个非负整数集合A‘, 所有属于A‘ 的集合的数x满足当且仅当能被表示成一些属于A 的元素的和(数字可重复). 比如, 当 A = {2,5,7}, 属于A‘ 的数为: 0 (0个元素的和), 2, 4 (2 + 2) and 12 (5 + 7 or 7 + 5 or 2 + 2 + 2 + 2 + 2 + 2); 但是元素1和3不属于A‘.

Input

第一行有一个整数n: 代表集合 A的元素个数, 1 <= n <= 5000. 接下来每行一个数ai描述一个元素, 1 <= ai <= 50000. A = {a1, a2, …, an}, a1 < a2 < … < an.

接下来一个整数k, 1 <= k <= 10000. 每行一个0 到 1000000000, 分别代表b1, b2, …, bk.

Output

输出k行. 第i行打印TAK, 如果 bi 属于A‘, 否则打印NIE.

Sample Input

2
5
7
6
0
1
4
12
3
2

Sample Output

TAK
NIE
TAK
TAK
NIE
TAK

题解

2054: 疯狂的馒头

Description

Input

第一行四个正整数N，M，p，q

Output

一共输出N行，第i行表示第i个馒头的最终颜色（如果最终颜色是白色就输出0）。

Sample Input

4 3 2 4

Sample Output

2
2
3
0

HINT

题解

3563: DZY Loves Chinese

Description

神校XJ之学霸兮，Dzy皇考曰JC。

摄提贞于孟陬兮，惟庚寅Dzy以降。

纷Dzy既有此内美兮，又重之以修能。

遂降临于OI界，欲以神力而凌♂辱众生。

今Dzy有一魞歄图，其上有N座祭坛，又有M条膴蠁边。

时而Dzy狂WA而怒发冲冠，神力外溢，遂有K条膴蠁边灰飞烟灭。

而后俟其日A50题则又令其复原。（可视为立即复原）

然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。

Input

第一行N,M

接下来M行x,y：表示M条膴蠁边，依次编号

接下来一行Q

接下来Q行：

每行第一个数K而后K个编号c1~cK：表示K条边，编号为c1~cK

为了体现在线，K以及c1~cK均需异或之前回答为连通的个数

Output

对于每个询问输出：连通则为‘Connected’，不连通则为‘Disconnected’

（不加引号）

Sample Input

5 10
2 1
3 2
4 2
5 1
5 3
4 1
4 3
5 2
3 1
5 4
5
1 1
2 7 0 3
6 0 7 4 6
1 2 7
0 5 0 2 13

Sample Output

Connected
Connected
Connected
Connected
Disconnected

HINT

N≤100000 M≤500000 Q≤50000 1≤K≤15

数据保证没有重边与自环

Tip：请学会使用搜索引擎

题解

5102: [POI2018]Prawnicy

Description

定义一个区间(l,r)的长度为r-l，空区间的长度为0。

给定数轴上n个区间，请选择其中恰好k个区间，使得交集的长度最大。

Input

第一行包含两个正整数n,k(1<=k<=n<=1000000)，表示区间的数量。

接下来n行，每行两个正整数l,r(1<=l<r<=10^9)，依次表示每个区间。

Output

第一行输出一个整数，即最大长度。

第二行输出k个正整数，依次表示选择的是输入文件中的第几个区间。

若有多组最优解，输出任意一组。

Sample Input

6 3
3 8
4 12
2 6
1 10
5 9
11 12

Sample Output

4
1 2 4

题解

2151: 种树

Description

A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。最终市政府给园林部门提供了m棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

Input

输入的第一行包含两个正整数n、m。第二行n个整数Ai。

Output

输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。

Sample Input

【样例输入1】
7 3
1 2 3 4 5 6 7
【样例输入2】
7 4
1 2 3 4 5 6 7

Sample Output

【样例输出1】
15

【样例输出2】
Error!
【数据规模】
对于全部数据：m<=n；
-1000<=Ai<=1000
N的大小对于不同数据有所不同：
数据编号 N的大小数据编号 N的大小
1 30 11 200
2 35 12 2007
3 40 13 2008
4 45 14 2009
5 50 15 2010
6 55 16 2011
7 60 17 2012
8 65 18 199999
9 200 19 199999
10 200 20 200000

2802: [Poi2012]Warehouse Store

Description

有一家专卖一种商品的店，考虑连续的n天。
第i天上午会进货Ai件商品，中午的时候会有顾客需要购买Bi件商品，可以选择满足顾客的要求，或是无视掉他。
如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。

Input

第一行一个正整数n (n<=250,000)。
第二行n个整数A1,A2,…An (0<=Ai<=10^9)。
第三行n个整数B1,B2,…Bn (0<=Bi<=10^9)。

Output

第一行一个正整数k，表示最多能满足k个顾客的需求。
第二行k个依次递增的正整数X1,X2,…,Xk，表示在第X1,X2,…,Xk天分别满足顾客的需求。

Sample Input

6
2 2 1 2 1 0
1 2 2 3 4 4

Sample Output

3
1 2 4

3709: [PA2014]Bohater

Description

在一款电脑游戏中，你需要打败n只怪物（从1到n编号）。为了打败第i只怪物，你需要消耗d[i]点生命值，但怪物死后会掉落血药，使你恢复a[i]点生命值。任何时候你的生命值都不能降到0（或0以下）。请问是否存在一种打怪顺序，使得你可以打完这n只怪物而不死掉

Input

第一行两个整数n,z(1<=n,z<=100000)，分别表示怪物的数量和你的初始生命值。
接下来n行，每行两个整数d[i],ai

Output

第一行为TAK（是）或NIE（否），表示是否存在这样的顺序。
如果第一行为TAK，则第二行为空格隔开的1~n的排列，表示合法的顺序。如果答案有很多，你可以输出其中任意一个。

Sample Input

3 5
3 1
4 8
8 3

Sample Output

TAK
2 3 1

2006: [NOI2010]超级钢琴

Description

小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的

音乐。这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。一个“超级

和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的

所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。

小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。

我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最

大值是多少。

Input

第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级和弦个数，L和R分别是超级和弦所

包含音符个数的下限和上限。接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。

N<=500,000

k<=500,000

-1000<=Ai<=1000,1<=L<=R<=N且保证一定存在满足条件的乐曲

Output

只有一个整数，表示乐曲美妙度的最大值。

Sample Input

4 3 2 3
3
2
-6
8

Sample Output

【样例说明】
共有5种不同的超级和弦：
音符1 ~ 2，美妙度为3 + 2 = 5
音符2 ~ 3，美妙度为2 + (-6) = -4
音符3 ~ 4，美妙度为(-6) + 8 = 2
音符1 ~ 3，美妙度为3 + 2 + (-6) = -1
音符2 ~ 4，美妙度为2 + (-6) + 8 = 4
最优方案为：乐曲由和弦1，和弦3，和弦5组成，美妙度为5 + 2 + 4 = 11。

3533: [Sdoi2014]向量集

[Submit][Status][Discuss]

Description

维护一个向量集合，在线支持以下操作：
“A x y (|x|，|y| < =10^8)”：加入向量(x，y);
“ Q x y l r (|x|，|y| < =10^8，1 < =L < =R < =T，其中T为已经加入的向量个数)询问第L个到第R个加入的向量与向量(x，y)的点积的最大值。
集合初始时为空。

Input

输入的第一行包含整数N和字符s，分别表示操作数和数据类别；
接下来N行，每行一个操作，格式如上所述。
请注意s≠’E’时，输入中的所有整数都经过了加密。你可以使用以下程序
得到原始输入：
inline int decode (int x long long lastans) {
return x ^ (lastans & Ox7fffffff);
}
function decode
begin
其中x为程序读入的数，lastans为之前最后一次询问的答案。在第一次询问之前，lastans=0。

注：向量(x，y)和(z，W)的点积定义为xz+yw。

Output

对每个Q操作，输出一个整数表示答案。

Sample Input

6 A
A 3 2
Q 1 5 1 1
A 15 14
A 12 9
Q 12 8 12 15
Q 21 18 19 18

Sample Output

13
17
17

解释：解密之后的输入为
6 E
A 3 2
Q 1 5 1 1
A 2 3
A 1 4
Q 1 5 1 2
Q 4 3 2 3

HINT

1 < =N < =4×10^5

1010: [HNOI2008]玩具装箱toy

Description

　　P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压
缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1…N的N件玩具，第i件玩具经过
压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容
器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一
个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，
如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容
器，甚至超过L。但他希望费用最小.

Input

　　第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

　　输出最小费用

Sample Input

5 4
3
4
2
1
4

Sample Output

2388: 旅行规划

Description

OIVillage是一个风景秀美的乡村，为了更好的利用当地的旅游资源，吸引游客，推动经济发展，xkszltl决定修建了一条铁路将当地n个最著名的经典连接起来，让游客可以通过火车从铁路起点（1号景点）出发，依次游览每个景区。为了更好的评价这条铁路，xkszltl为每一个景区都哦赋予了一个美观度，而一条旅行路径的价值就是它所经过的景区的美观度之和。不过，随着天气与季节的变化，某些景点的美观度也会发生变化。

xkszltl希望为每位旅客提供最佳的旅行指导，但是由于游客的时间有限，不一定能游览全部景区，然而他们也不希望旅途过于短暂，所以每个游客都希望能在某一个区间内的车站结束旅程，而xkszltl的任务就是为他们选择一个终点使得旅行线路的价值最大。可是当地的景点与前来观光的旅客实在是太多了，xkszltl无法及时完成任务，于是找到了准备虐杀NOI2011的你，希望你能帮助他完成这个艰巨的任务。

Input

第一行给出一个整数n，接下来一行给出n的景区的初始美观度。

第三行给出一个整数m，接下来m行每行为一条指令：

\1. 0 x y k：表示将x到y这段铁路边上的景区的美观度加上k；

\2. 1 x y：表示有一名旅客想要在x到y这段（含x与y）中的某一站下车，你需要告诉他最大的旅行价值。

Output

对于每个询问，输出一个整数表示最大的旅行价值。

Sample Input

5
1 8 -8 3 -7
3
1 1 5
0 1 3 6
1 2 4

Sample Output

9
22

HINT

Data Limit:

对于20%的数据，n，m≤3000；

对于40%的数据，n，m≤30000；

对于50%的数据，n，m≤50000；

另外20%的数据，n，m≤100000，修改操作≤20；

对于100%的数据，n，m≤100000。