## 【BZOJ 3884】上帝与集合的正确用法

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c = getchar();
int ret = 0, f = 1;
while (c < '0' || c > '9') {
f = c == '-'? -1: 1;
c = getchar();
}
while ('0' <= c && c <= '9') {
ret = ret * 10 + c - '0';
c = getchar();
}
return ret * f;
}

inline int get_phi(int x) {
int ret = x;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
ret = ret / i * (i - 1);
while (x % i == 0) {
x /= i;
}
}
}
return x == 1? ret: ret / x * (x - 1);
}

inline int Pow(int w, int t, int MOD) {
int ret = 1;
for (; t; t >>= 1, w = (LL)w * w % MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}

inline int f(int p) {
if (p == 1) {
return 0;
} else {
int phi = get_phi(p);
return Pow(2, f(phi) + phi , p);
}
}

int main() {
for (int i = read(); i; --i) {
}
return 0;
}


## 【Codeforces 757E】Bash Plays with Functions

### 解题报告

Ⅰ. 设$x$的素因子种类数为$g(x)$那么$f_0(x)$等于$2^{g(x)}$
Ⅱ. 由规律Ⅰ可得，$f_0(x)$为积性函数，又$f_i(x)=f_{i-1} * 1(x)$，于是我们可用归纳证明得$f_i(x)$均为积性函数
Ⅲ. 设$p$为素数，$f_r(p^k)$与$p$无关，且满足递推式：$f_r(p^k)=\sum\limits_{i=0}^{k}{f_{r-1}(p^i)}$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000009;
const int MOD = 1000000007;

int tot,vis[N],pri[N],sur[N],g[N][21];

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void prework() {
for (int i=2;i<N;i++) {
if (!vis[i]) pri[++tot] = i, sur[i] = i;
for (int j=1;j<=tot&&i*pri[j]<N;j++) {
vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
g[0][0] = 1;
for (int i=1;i<=20;i++) g[0][i] = 2;
for (int i=1;i<N;i++) {
for (int j=0;j<=20;j++) {
g[i][j] = ((j? g[i][j-1]: 0) + g[i-1][j]) % MOD;
}
}
}

inline int solve(int a, int b) {
int ret = 1;
for (int cnt=0,p=sur[b];b>1;cnt=0,p=sur[b]) {
while (b % p == 0) b /= p, cnt++;
ret = (LL)ret * g[a][cnt] % MOD;
}
return ret;
}

int main() {
prework();
printf("%d\n",solve(a,b));
}
return 0;
}


## 【51NOD 1135】原根

### 解题报告

wiki上给出了这样一个上界：$O(n^{0.499})$，但$n$要大于$e^{e^{24}}$，所以对于OI题没什么用QwQ

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline int Get_Primitive_Root(int w) {
vector<int> pri;
for (int i=2,lim=ceil(sqrt(w)),cur=w-1;i<lim;i++) {
if (cur % i == 0) {
pri.push_back(i);
while (cur % i == 0)
cur /= i;
}
if (cur > 1 && i == lim - 1)
pri.push_back(cur);
}
static auto Pow = [](int w, int t, int MOD) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD)
if (t & 1) ret = (LL)ret * w % MOD;
return ret;
};
if (!pri.size()) return 2;
for (int i=2;i<=w;i++) {
for (int j=pri.size()-1;~j;j--) {
if (Pow(i,w/pri[j],w) == 1) break;
if (!j) return i;
}
}
}

int main() {
return 0;
}


## 【POJ 1737】Connected Graph

_(:з」∠)_

## 【COGS 741】[网络流24题] 负载平衡

6541324587

#include<bits/stdc++.h>
using namespace std;

const int N = 100+9;

int n,arr[N],sum,vout,sta;

char c=getchar(); int ret = 0, f = 1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

int main(){
for (int i=1;i<=n;i++) sum += (arr[i] = read()); sum /= n;
for (int i=1;i<=n;i++) arr[i] -= sum - arr[i-1];
nth_element(arr+1,arr+n/2,arr+n); sta=arr[n/2];
for (int i=1;i<=n;i++) vout += abs(arr[i]-sta);
cout<<vout<<endl;
return 0;
}


## 【Codeforces 711E】ZS and The Birthday Paradox

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
#define pow POW
using namespace std;

const LL MOD = 1000003;

char c=getchar(); LL ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
return ret*f;
}

inline LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = ret*w % MOD;
w = w*w % MOD; t >>= 1;
}
return ret;
}

inline bool judge(LL n, LL k) {
LL w = 1;
for (int i=1;i<=n;i++) {
w *= 2;
if (w >= k) return false;
} return true;
}

int main(){
if (judge(n,k)) cout<<1<<' '<<1;
else {
LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
cout<<t1<<' '<<t2;
}
return 0;
}


ps:如果不知道上面的那个定理，貌似自己推也是可以推出来的？

## 【Codeforces 707C】Pythagorean Triples

### Code

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;

LL a,b,c;

int main(){
cin>>a; a *= a;
if (a <= 4) cout<<-1;
else if (a & 1) cout<<a/2<<' '<<a/2+1;
else cout<<a/4+1<<' '<<a/4-1;
return 0;
}


## 【算法笔记】线性筛 与 线性递推

get_phi_prime_mu_in_linear_time

ps:之前好像说必须先O(n)筛出素数？现在发现好像不需要QAQ（模板参考BZOJ_2705）

## 【POJ 1284】Primitive Roots

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 100000+9;
const int MX = 70000;

int pri[MAXN],tot,phi[MAXN];
bool tag[MAXN];

inline void Get_Phi(){
phi[1] = 1;
for (int i=2;i<=MX;i++) {
if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
for (int j=1;j<=tot && pri[j]*i <= MX;j++) {
tag[pri[j]*i] = 1;
if (i % pri[j]) phi[pri[j]*i] = phi[i]*(pri[j]-1);
else {phi[pri[j]*i] = phi[i]*pri[j]; break;}
}
}
}

int main(){
Get_Phi(); int a;
while (~scanf("%d",&a))	printf("%d\n",phi[a-1]);
return 0;
}