模板部分：
#define LL long long
#define FF(i,n) for(i=0;i<n;i++)
LL f[N];
LL ans[N];
LL init[N];
LL buf[N];
void matrixMul(LL a[N],LL b[N],LL n,LL mod)
{
int i,j;
FF(i, n) buf[i]=0;
FF(i, n) FF(j,n) if(a[(i - j + n) % n] && b[j])
buf[i] = (buf[i] + a[(i - j + n) % n] * b[j]);
FF(i, n) a[i] = buf[i] % mod; // 算完后再取模，节省时间
}
void matrixMul(int n,int m,int mod)
{
int i,j;
FF(i,n) ans[i] = (i==0);
while(m > 1)
{
if(m&1) matrixMul(ans, init, n, mod);
matrixMul(init, init, n, mod);
m >>= 1;
}
matrixMul(init, ans, n, mod);
}
UVALive 4727 Jump 约瑟夫变形问题
模板部分：
LL gcd(LL a, LL b)
{
return b == 0 ? a : gcd(b, a % b);
}
void E_gcd(LL a, LL b, LL &d, LL& x, LL& y)
{
if(!b)
{
d = a;
x = 1, y = 0;
}
else
{
E_gcd(b, a % b, d, y, x);
y -= x*(a / b);
}
}
hdu 4497 GCD and LCM 质分解
模板部分：
const int N = 111111;
vector<int> hav;
bool isp[N];
int p[N], cnt;
void getp()
{
int i, j;cnt = 0;
isp[0] = isp[1] = 1;
for(i = 2; i < N; i ++)
{
if(!isp[i])
{
p[cnt ++] = i;
if(i <= 1111)for(j = i * i; j < N; j += i) isp[j] = 1;
}
}
}
void get_hav(int h) //求h的所有质因数（算重复）
{
int i;
for(i = 0; i < cnt && h > 1; i ++)
{
if(h % p[i] == 0)
{
h /= p[i];
hav.push_back(p[i]);
i --;
}
}
if(h != 1) hav.push_back(h);
}
hdu 4418 Time travel 高斯消元
模板部分：
inline int sgn(double d) {
if (fabs(d) < eps) return 0;
return d > 0 ? 1 : -1;
}
int gauss(int N, int M){
int i, j, r, c, pvt;
double maxp;
for (r = 0, c = 0; r < N && c < M; ++ r, ++ c) {
for (maxp = 0, i = r; i < N; ++ i)
if (fabs(a[i][c])>fabs(maxp)) maxp = a[pvt=i][c];
if (sgn(maxp) == 0) {
r--;
continue;
}
if (pvt != r)
for (j = r; j <= M; ++j) swap(a[r][j], a[pvt][j]);
for (j = c+1; j <= M; ++j) {
a[r][j] /= maxp;
for (i = r+1; i < N; ++i)
a[i][j] -= a[i][c]*a[r][j];
}
}
for (i = r; i < N; ++i)
if (sgn(a[i][M])) return -1;
if (r < M) return M-r;
for (i = M-1; i >= 0; --i)
for (j = i+1; j < M; ++j)
a[i][M] -= a[j][M]*a[i][j];
return 0;
}
ZOJ 2320 Cracking' RSA 其次布尔线性方程组，高斯消元。
int gauss(int N, int M)
{
int r, c, pvt;
bool flag;
for (r = 0, c = 0; r < N && c < M; ++ r, ++ c) {
flag = false;
for (int i = r; i < N; ++ i)
if (a[i][c]) {
flag = a[pvt=i][c];
break;
}
if (!flag) {
r--; continue;
}
if (pvt != r)
for (int j = r; j <= M; ++j) swap(a[r][j], a[pvt][j]);
for (int i = r+1; i < N; ++i)
if(a[i][c])
{
a[i][c] = false;
for (int j = c+1; j <= M; ++j) {
if(a[r][j]) a[i][j] = !a[i][j];
}
}
}
return r; //return的是系数矩阵的秩
}
hdu 4746 Mophues 莫比乌斯反演
模板部分：
void Mobius()
{
CLR(isp, 0);CLR(cnt, 0);
int tot = 0;mob[1] = 1;
for(int i = 2; i < N; i ++)
{
if(!isp[i])
{
p[tot ++] = i;
mob[i] = -1;cnt[i] = 1;
}
for(int j = 0; j < tot && p[j] * i < N; j ++)
{
isp[p[j] * i] = true;
cnt[i * p[j]] = cnt[i] + 1;
if(i % p[j] == 0)
{
mob[p[j] * i] = 0;
break;
}
else
{
mob[p[j] * i] = -mob[i];
}
}
}
}
分块处理：
for(int i = 1, j = 1; i < n; i = j + 1)
{
j = min(n / (n / i), m / (m / i));
ans += (LL)(mbs[j][p] - mbs[i - 1][p]) * (n / i) * (m / i);
}
容斥原理：
void dfs(int st, LL now) ///num表示元素个数。
{
ans.insert(now);
if(st >= tot) return;
LL tmp = 1;
for(int i = 0; i <= num[st]; i ++)
{
dfs(st + 1, now * tmp);
tmp *= bef[st];
}
return ;
}