逆元：对于a和p，若 a * inv(a) % p ≡ 1，则称inv(a)为a%p的逆元。其中p为质数逆元就是在mod下，不能直接除以一个数，而要乘以他的逆元a * inv(a) = 1 (mod p)x / a可以改成 x * inv(a) % p 方法一.扩展欧几里得 a * inv(a) = 1 (mod p)可以变形成 a * inv(a) +k * p = 1(前提是a和p要互素)可以用扩欧的公式来计算时间复杂度:O(logn)适用范围：只要存在逆元即可求，适用于个数不多但是mod很大的时候，也是最常见的一种求逆元的方法。 代码： ll exgcd(ll a,ll b,ll &am...

来源：牛客网@[toc] 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 131072K，其他语言262144K 64bit IO Format: %lld 题目描述  定义S(n) = 12 + 22 + … + n2，输出S(n) % 1000000007。 注意：1 < n < 1e18。  输入描述:  多组输入，输入直到遇到EOF为止； 第一行输入一个正整数n。  输出描述:  输出S(n) % 1000000007的结果。  示例1输入 1 2 1000 输出 1 5 333833500 题解： 平方和公式：1^2^+2^2^+3^2^+......+n...

@[toc]Poj 1284 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 6485 Accepted: 3697 Description  We say that integer x, 0 < x < p, is a primitive root modulo odd primep if and only if the set { (xi mod p) | 1 <= i <= p-1 } is equal to {1, ..., p-1 }. For example, the consecutiv...

HDU 2504@[toc] Problem Description  有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。  Input  第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。  Output  输出对应的c，每组测试数据占一行。  Sample Input 2 6 2 12 4 Sample Output 4 8 题解： 单纯的暴力就能过。。。。也可以加点小优化，gcd(a,c)=b,那么gcd(a/b,c/b)=1,所以枚举 i ,使得 i 满足gcd（a/...

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26063 Accepted: 17394 @[toc]Poj 3070 Fibonacci Description  In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 +Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonaccisequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...

hdu 1525@[toc] Problem Description  Two players, Stan and Ollie, play, starting with two natural numbers.Stan, the first player, subtracts any positive multiple of the lesserof the two numbers from the greater of the two numbers, provided thatthe resulting number must be nonnegative. Then Ollie, the...

欧几里得算法： 求a，b的最大公约数gcd（a,b）= gcd(b,a%b) ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } 扩展欧几里得算法： 如果a，b是整数，一定存在x和y使得ax+by=gcd（a，b）也就是ax+by=m的话,m一定是gcd（a，b）的倍数 假设当前我们在求的时a和b的最大公约数，而我们已经求出了下一个状态：b和a%b的最大公因数，并且求出了一组x1和y1使得 ： b * x1+(a%b) * y1 = gcd结论： x = y1 , y = x1 – a / b * y1得到的是特解，如何由特解推出其他的整数解：对于关...

Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 143491 Accepted: 33018 Description  @[toc]题目传送 题目：  两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具***置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为...

@[toc]hdu 1576 题目：  要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。  Input  数据的第一行是一个T，表示有T组数据。 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。  Output  对应每组数据输出(A/B)%9973。  Sample Input 2 1000 53 87 123456789 Sample Output 7922 6060 题解： 先了解一些概念：费马小定理：a^p−1^≡1 (mod p) ，其...

@[toc] 普通矩阵（单个矩阵值为任何数） 例题：POJ 1074求出其中最大的子矩阵答案是：9 2-4 1-1 8最大和是15我们先想想如果不是矩阵，是一个数组，求其中连续的最长一段，咋做？ 最大子段和 我们用b[i]来表示a[0].....a[1]的最大子段和那么b [ i ] =max ( b [i - 1 ] + a [ i ], a [ i ] )当a[n] 大于dp[n-1]（前n-1个元素序列的最大子段和）。此时舍弃前面的子段和，即断开。否则的话，把a[n]连接到前n-1个元素序列的最大和子段上，即dp[n] = dp[n-1] + a[n] int MaxSum(int n,...

P4015 运输问题@[toc] 题目描述：  输入格式：  输出格式： 两行分别输出最小运输费用和最大运输费用。 输入输出样例： 输入 #1 2 3 220 280 170 120 210 77 39 105 150 186 122 输出 #1 48500 69140 题解： 最小费用最大流(MCMF)问题根据样例数据分析：橙色为第一个仓库晕倒各零售商店的单位费用绿色为第二个一边是仓库，一边是商店，典型的二分图，还是完全二分图我们可以在仓库的左边设置一个源点S，右边设置一个终点T。S指向每一个仓库，容量为ai，费用为0，而每一个商店指向T，容量为bi，费用为0从仓库到商店的边容量是min（仓...

P4011 孤岛营救问题@[toc] 输入输出样例 输入 4 4 9 9 1 2 1 3 2 1 2 2 2 0 2 1 2 2 0 2 1 3 1 0 2 3 3 3 0 2 4 3 4 1 3 2 3 3 0 3 3 4 3 0 4 3 4 4 0 2 2 1 2 4 2 1 输出  14 题意： (原题太长我就不贴了，简单叙述一下)一个N*M的迷宫，每个单元格之间可能有门或者墙，也可能啥也没有。门和墙的总数为K（会读入墙和门的位置坐标）门存在种类，只有拥有对应种类的钥匙才可以打开这类门钥匙的总量为S（会读入钥匙的坐标）从一个单元格到另一个单元格时间为1现在从左上角（1,1）出发，到右下角...

@[toc]P4016 负载平衡问题 题目描述  G 公司有 n 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 n个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。  输入格式  第一行一个正整数 n，表示有 n 个仓库。 第二行 n 个正整数，表示 n 个仓库的库存量。  输出格式输出最少搬运量。 输入输出样例输入 #1复制 5 17 9 14 16 4 输出 #1复制 11 说明/提示1≤n≤100。 题解： 和网络流啥关系。。。又是老婆饼里没老婆？ 方法一： 环形均分纸牌问题，还是板子题，代码都是通用的。。 贪心+数论这种题总感觉在哪见过。。...

均分纸牌有三种情况：线性，环形，二维@[toc] 线性 题目描述 P1031 均分纸牌有N堆纸牌，编号分别为1,2,…,N。每堆上有若干张，但纸牌总数必为N的倍数。可以在任一堆上取若干张纸牌，然后移动。移动规则:只能向相邻的纸牌移动问最少移动多少次可以使纸牌数一样多 思路： 第一堆只能给第二堆多干张，或者第二堆给第一堆，这取决于第一堆的初始牌量。当确定第一堆状态后，我们就不用再考虑他，第二堆就变成新的第一堆。所以我们先求平均值（也就是最终每堆多少张），然后从第一堆开始往后一次比较，如果相等就跳过，如果不是，移动次数就加1比如：1 1 1 9平均值为3第四堆多6张，全部移动到第三堆，然后第三堆再...