费马小定理（欧拉定理的一种特殊情况）如果p是一个质数的话，那对于任意一个数a，a的n次方减去a之后都将是n的倍数。  a^p-a=k*p => (a^p-a)%p=0 => a^p≡a(mod p)对于质数p，任意整数a，均满足a^(p-1)≡1(mod p)如果整数a不是p的倍数，a^(p-1)≡1(mod p)如果a不是p的倍数，a^p≡a(mod p)如果a不是p的倍数，a^(p-1)≡1(mod p)若x是一个不能被质数p整除的整数，则x^(p-1)-1必能被p整除。x^(p-1)≡1(mod p) 未完待续。。。

//求x^y%mod ll quick(ll x,ll y,ll mod){ ll ans=1; while(y){ if(y&1) ans=ans*x%mod; x=x*x%mod; y/=2; } return ans; }//求a^n%mod (mod 在前面定义了) ll quick(ll a,ll n) { ll re=1; while(n) { if(n&1) //判断n的二进制最后一位是不是1，或者说判断n是不是奇数 { re=(re*a)%mod; } n>>=1; //除掉n二进制的最后一位，相当于/2 a=(a*a)%mod; } return ...

首先介绍几个简单的概念： 1.m|(a-b）：表示(a-b)被m整除设a%m=c,则b%m=c;也就是说a和b除以m的余数是相同的。举一个例子：3|(11-5)11%3=2,5%3=2,(11-5)%3=0 大体就是这个意思。 2.同余：设m是大于1的正整数,a,b是整数,如果m|(a-b),则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余.【同余的主要性质】：  (a+b)%d=(a%d+b%d)%d 加减乘除都能分开写要注意的是减法，因为减法可能会减出来负值所以可以这样写（a-b+mod）%mod； 下面是威尔逊定理： 在初等数论中，威尔逊定理给出了判定一个自然数是否...

题目链接：https://vjudge.net/contest/373557#problem/I 题目大意：求 重新编码后的 最短长度 和 重新编码后的 最长字符串的长度 数据结构刚学了Huffman树，比赛就考到了Huffman编码，在这里整理一下。 Huffman树是最优二叉树，这道题相当于最优k叉树，但是又有些不同。 不会Huffman树的可以从百度搜索，这里就不具体讲了。 Huffman树是在队列中挑出最小的两个权值组成一新节点，并放入队列中。 在这道题里面，并不是二进制，而是K进制，所以想要用到Huffman树，必须要满足(n-1)%(k-1)==0，这个条件的意思就是：最后合并的时...

struct sss { int x,y; inline friend bool operator <(const sss &a , const sss &b) { return a.x>b.x; //从大到小排列 } }a[100];普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。 在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。 和队列基本操作相同: top 访问队头元素 empty 队列是否为空 size 返回队列内元素个数 pu...

试题链接：https://vjudge.net/problem/POJ-1088 这道题肯定最先想到是DFS跟BFS，但是数据是100*100，还要每个点都进行搜索，肯定会超时。 但是我为了巩固DFS跟BFS，把这道题的BFS跟DFS都码了一遍，如果这道题数据没有这么大的话，肯定是可以的。 下面的代码是BFS跟DFS的代码，都TE了。 TE BFS #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm>...

题目链接：Charm Bracelet POJ 3624 #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> using namespace std; int w[20000...

题目链接：POJ 1458 #include <cstdio> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> using namespace std; string s1,s2; int a[1005][...

https://blog.csdn.net/Ven21959/article/details/99057467?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task

问题链接：http://acm.upc.edu.cn/OnlineJudge/problem.php?cid=1008&pid=0 这是一个经典题目"凸多边形最优三角形剖分",解法是区间dp。 dp[i][j] 表示从第i到第j个点最优剖分 的答案。 当 j=i 或 j=i+1 时，无法构成三角形， dp[i][j]=0 。 当 j>=i+2 时，考虑一个分割点k, ijk 三点构成一个三角形，此时划分为i到k部分，k到j部分，以及三角形ijk部分这三个部分。i到k部分和k到j 部分是子问题，可以利用之前求出的结果，三角形ijk的值是三点权值之积。  #inc...

set是关联式容器。set作为一个容器也是用来存储同一数据类型的数据结构，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，并且系统能根据元素的值自动进行排序。 头文件：#include<set> 定义： set<数据类型>s; 插入： s.insert(); 输出： （用迭代器） for (set<int>::iterator it=s.begin();it!=s.end();it++) { cout << *it << endl; } 返回>=某一特定的值： *s.lower_bound(特定的值); 返回&gt...

试题链接：最长上升子序列：POJ 2533如何把这个问题分解成子问题呢？“求序列的前n个元素的最长上升子序列的长度F(n)”是一个子问题，但这样分解子问题，不具有“后无效性”。假设F(n)=x，但可能有多个序列满足F(n)=x。有的序列的最后一个元素比小，不能和形成一个更长的上升子序列······以后的事情（求F(n+1),F(n+2),···）受如何达到状态n的影响，因此F(n)这样的子问题分解方法不符合“后无效性”。  “后无效性”：当前的若干个状态值一旦确定，则此后过程的演变就只和这若干个状态的值有关，与之前是采取哪种手段或经过哪条路径演变到当前的若干个状态无关。 经过分析，发现“求以(...

求从N*M矩形的左上角到右下角两条路径的最大值下面的代码中：a[i][j]代表：任意一点的路程b[i][j][k][l]代表：一点在i,j处，另一点在k,l处时所能取得的最大值 #include <cstdio> #include <iostream> #include <cmath> using namespace std; int a[55][55]; int b[55][55][55][55]; int main () { int n,m; cin >> n >> m; for (int i=1;i<=n;i++) { f...