一般对于 a^b%p 的形式当b很大，大到long long都存不小时，就不能直接快速幂了，必须对b取模，但不是直接让b对p取模，为什么呢？因为是错的。 这个时候我们怎么办呢？ 这个时候我们就要用到欧拉降幂了。 上面就是欧拉降幂的公式，一般来说，我们使用第三个即可。 phi 就是欧拉函数。 下面给出求欧拉函数的板子 ll phi(ll n) { ll i,rea=n; for(i=2;i*i<=n;i++) { if(n%i==0) { rea=rea-rea/i; ...

gcd( F [ n + 1 ] , F [ n ] ) = 1 gcd(f[n],f[m]) = f[gcd(n,m)]   1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1。   可以用于斐波那契数列求前缀和，然后在用矩阵快速幂求出答案。   2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)。   与上面相似，不过是奇数前缀和。   3.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1。   与上面相似，不过是偶数前缀和。   4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)。   与...

看到这道题，首先应该就想到了求因子，但是计算的时候，又会有重复，就很麻烦，所以我们需要素数这个东西。 问题所要求的是 gcd( x , n ) > m ,由gcd( x , n )本身可知，gcd求出来的是 x 和n的最大公约数（设为a），即有式子gcd( x ,n )=a , 进一步进行化简可变为gcd( x/a , n/a )=1 , 到了此处这个式子又有了另一层含义——x/a与n/a互素 。在联想到欧拉函数的功能——对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。于是将欧拉函数里的n换成n/a，不就正好能求出x/a的个数了吗？x/a的个数不就是我们所要求的x的个数了吗...

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Althoug...

先给出百度百科的概念： n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。 错排数怎么计算呢？ n 的错排数我们用 D[n] 来表示: 第一步，考虑第n个元素，把它放在某一个位置，比如位置k，一共有n-1种放法； 第二步，考虑第k个元素，这时有两种情况：（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有 D[n-2] 种放法；（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有 D[n-1] 种放法。 根据乘法和加法法则，综上得到 D[n] = (n...

最小顶点覆盖：在二分图中寻找一个尽量小的点集，使图中每一条边至少有一个点在该点集中。 最小顶点覆盖 == 最大匹配。      反证法证明：假设当前存在一条两个端点都不在最小顶点覆盖点集中，那么这么光芒四射的边定可以增大最大匹配边集，与最大匹配矛盾，所以得证。 最小路径覆盖：在二分图中寻找一个尽量小的边集，使图中每一个点都是该边集中某条边的端点。 最小路径覆盖 == 顶点数 - 最大匹配。      证明：因为一条边最多可以包含两个顶点，所以我们选边的时候让这样的边尽量多，也就是说最大匹配的边集数目咯。剩下的点就只能一个边连上一个点到集合里啦。 最大独立集：在N个点中选出来一个...

Flight Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others) Total Submission(s): 5058 Accepted Submission(s): 1146 Problem Description Recently, Shua Shua had a big quarrel with his GF. He is so upset that he decides to take a trip to some other city to avoid meeting ...

Problem Description There are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black ...

Assign the task Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description There is a company that has N employees(numbered from 1 to N),every employee in the company has a immediate boss (except for the leader of whole company).If you are the immediate bo...

Apple Tree Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 39797 Accepted: 11814 Description There is an apple tree outside of kaka’s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree. The tree ...

再来一个简单的分层图练习： 题目描述 Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为0到n-1，一共有m种航线，每种航线连接两个城市，并且航线有一定的价格。 Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bob这次出行最少花费多少？ 输入格式 数据的第一行有三个整数，n,m,k，分别表示城市数，航线数和免费乘坐次数。 第二行有两个整数，s,ts,t，分别表示他们出行的起点城市编号和终点城...

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科 比如在上面这幅图当中： ( LCA(A,B) ---- 表示A,B的最近公共祖先。) LCA ( 2 , 7 ) == 1 ; LCA ( 4 , 8 ) == 1 ; LCA ( 6 ,10) == 1; LCA ( 5 , 6 ) == 4 ; 相信你应该理解,LCA,是什么了吧 ， 那么怎么求LCA呢？ 这里我们有两种在线的算法： 暴力 倍增 暴力虽然可以计算，但是碰到数据大的题目，肯定会被 T 到飞起。 所...

How far away ？ Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 30216 Accepted Submission(s): 12180 Problem Description There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this ...

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others. Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a c...