## 【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;
}


## 【日常小测】题目2

std的话非常套路啊！

### Code

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

const int N = 100009;

LL vout[N],cnt[N],ans;
int n,m,tot,BLK,pri[N],arr[N],phi[N];
vector<int> divs[N]; bool vis[N];
struct Query{int l,r,id,blk;}q[N];

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 void Modify(int w, int t) {
for (int j=divs[w].size()-1,c;~j;j--) {
c = divs[w][j];
if (~t) ans += cnt, cnt += phi;
else cnt -= phi, ans -= cnt;
}
}

int main() {
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
n = read(); BLK = sqrt(n) + 1; phi[1] = 1;
for (int i=2;i<=n;i++) {
if (!vis[i]) phi[i] = i-1, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
vis[i*pri[j]] = 1;
if (i % pri[j]) phi[i*pri[j]] = phi[i] * phi[pri[j]];
else {phi[i*pri[j]] = phi[i] * pri[j]; break;}
}
}
for (int i=1;i<=n;i++) {
for (int j=i;j<=n;j+=i)
divs[j].push_back(i);
for (int i=1;i<=m;i++) {
q[i].id = i; q[i].blk = q[i].l / BLK;
}
sort(q+1, q+1+m, [](const Query &A, const Query &B){return A.blk<B.blk||(A.blk==B.blk&&A.r<B.r);});
for (int i=1,l=1,r=0;i<=m;i++) {
while (r > q[i].r) Modify(arr[r--], -1);
while (r < q[i].r) Modify(arr[++r], 1);
while (l > q[i].l) Modify(arr[--l], 1);
while (l < q[i].l) Modify(arr[l++], -1);
vout[q[i].id] = ans;
}
for (int i=1;i<=m;i++) printf("%lld\n",vout[i]);
return 0;
}


## 【BZOJ 2190】[SDOI2008] 仪仗队

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

const int MAXN = 40000+9;

int n,pri[MAXN],tot,phi[MAXN];
bitset<MAXN> tag;

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

int main(){
scanf("%d",&n); n-=1;
Get_Phi();
printf("%d\n",phi[n]*2-1+2);
return 0;
}


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

const int MAXN = 100000+9;

int n,m,pri[MAXN],tot,tmp;
LL phi[MAXN],vout;
bitset<MAXN> tag;

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

int main(){
scanf("%d%d",&n,&m);
if (n > m) swap(n, m); Get_Phi();
for (int i=1;i<=n;i=tmp+1){
tmp = min(n/(n/i),m/(m/i));
vout += (LL)(phi[tmp]-phi[i-1])*(n/i)*(m/i);
}
printf("%lld\n",vout*2-(LL)n*m);
return 0;
}


（x,y）这个点到原点的连线上整点的个数为gcd(x,y)

—————————— UPD 2017.2.1 ——————————

—————————— UPD 2017.7.3 ——————————

## 【BZOJ 2818】Gcd

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

const int MAXN = 10000000+9;

int pri[MAXN],tot,mu[MAXN],n;
bitset<MAXN> tag;

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

int main(){
scanf("%d",&n); Get_mu(); LL vout = 0;
for (int j=1;j<=tot && pri[j] <= n;j++) {
int k = pri[j], a=n/k;
for (int i=1,tmp;i<=a;i=tmp+1)
tmp = a/(a/i),
vout += (LL)(mu[tmp]-mu[i-1])*(a/i)*(a/i);
}
printf("%lld\n",vout);
return 0;
}


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

const int MAXN = 10000000+9;

int pri[MAXN],tot,n;
LL phi[MAXN],vout=0;
bitset<MAXN> tag;

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

int main(){
scanf("%d",&n); Get_Phi();
for (int i=1;i<=tot && pri[i] <= n;i++)
vout += phi[n/pri[i]]*2 - 1;
printf("%lld\n",vout);
return 0;
}


## 【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;
}