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

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3884
官方题解:http://blog.csdn.net/popoqqq/article/details/43951401

解题报告

根据欧拉定理有:$a^x \equiv a^{x \% \varphi (p) + \varphi (p)} \mod p$
设$f(p)=2^{2^{2 \cdots }} \mod p$
那么有$f(p) = 2^{f(\varphi(p)) + \varphi(p)} \mod p$

如果$p$是偶数,则$\varphi(p) \le \frac{p}{2}$
如果$p$是奇数,那么$\varphi(p)$一定是偶数
也就是说每进行两次$\varphi$操作,$p$至少除$2$
所以只会递归进行$\log p$次
总时间复杂度:$O(T\sqrt{p} \log p)$

Code

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

inline int read() {
	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) {
		printf("%d\n", f(read())); 
	}
	return 0;
}

【日常小测】题目2

相关链接

题目传送门:http://paste.ubuntu.com/24087843/
数据生成器:http://paste.ubuntu.com/24087850/
std:http://paste.ubuntu.com/24087841/

题目大意

给定$1 \sim n$的排列$a_i$,再给定$m$个询问、每次给出$l_i,r_i$
求$\sum\limits_{i=l_i}^{r_i}{\sum\limits_{j=l_i}^{i-1}{gcd(a_i,a_j)}}$, $n,m \le 2 \cdot 10^4$

解题报告

一看数据范围就给人一种大暴力的感觉
但用$O(1)$的$GCD$做到$O(nk)$并不能通过此题

std的话非常套路啊!
考虑维护一个集合,支持加入、删除、查询集合中的数两两$GCD$的和
如果可以在$O(\log n)$的时间复杂度完成维护的话,显然可以用莫队做到$O(n^{1.5} \log n)$

现在考虑如何维护,如果分解因数的话,会有算重的部分
但我们列出式子,发现我们计算的实际是:$\sum\limits_{d|gcd(a_i,a_j)}{f(d)}$
如果窝萌把$f(d)$令成$\varphi (d)$,那岂不是刚刚好?
于是我们对于删除和加入,枚举因数$i$,然后在第i个位置加入$\varphi (i)$即可
那么总的复杂度均摊下来是$O(n^{1.5} \log n)$的

另外本题还有一个兄弟版本:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1439
就是要求维护一个集合中两两互质的对数,把$\varphi(i)$换成$\mu(i)$就是一样的做法了
全™是套路啊!

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];

inline int read() {
	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++) {
		arr[i] = read();
		for (int j=i;j<=n;j+=i)
			divs[j].push_back(i);
	} m = read();
	for (int i=1;i<=m;i++) {
		q[i].l = read(); q[i].r = read();
		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] 仪仗队

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2190
离线版题目:http://paste.ubuntu.com/20271981/

这个是“能量采集”的弱化版,所以mu和phi都可以很简单做
线筛写错了,wa了好久QAQ

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

【BZOJ 2005】[Noi2010] 能量采集 Advance

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2005
前传传送门:http://oi.cyo.ng/?p=477

之前%JCVB的没有成功。
今天又来%,基本上有思路了,真的是_(:з」∠)_

引理:\(\varphi (n) = \sum\limits_{d|n} {\frac{n}{d} \cdot \mu (d)}\)
证明:\(\varphi (n) = \sum\limits_{i = 1}^n {[\gcd (i,n) = = 1] = \sum\limits_{i = 1}^n {\sum\limits_{d|i} {\sum\limits_{d|n} {\mu (d) = \sum\limits_{d|n} {\mu (d) \cdot \sum\limits_{i = 1}^n {[\gcd (i,n) = = i] = } } } } } } \sum\limits_{d|n} {\mu (d) \cdot \frac{n}{d}}\)

我们之前的式子是:\(\sum\limits_{d = 1}^n {\sum\limits_{k = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {d \cdot \mu (k) \cdot \left\lfloor {\frac{n}{{d \cdot k}}} \right\rfloor } } \cdot \left\lfloor {\frac{m}{{d \cdot k}}} \right\rfloor\)
注意看好,我要变形啦!( •̀ ω •́ )y
不妨设:D=k*d,则有原式=\(\sum\limits_{D = 1}^n {\sum\limits_{d|D} {d \cdot \mu (\frac{D}{d}) \cdot } } \left\lfloor {\frac{n}{D}} \right\rfloor \cdot \left\lfloor {\frac{m}{D}} \right\rfloor \)
根据引理可以进一步简化为:\(\sum\limits_{D = 1}^n {\varphi ({\rm{D}})} \cdot \left\lfloor {\frac{n}{D}} \right\rfloor \cdot \left\lfloor {\frac{m}{D}} \right\rfloor \)
然后就可以线筛出欧拉函数后,\(\sqrt n \)分块就好,总时间复杂度:O(n)

#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)
为什么会有这个结论呢?
因为这个相当于把线段分成了完全相同的gcd(x,y)段
或者可以这样理解:
离原点最近的一个肯定是(x/gcd(x,y),y/gcd(x,y))
之后的每一整点都是他的整数倍,所以总共有gcd(x,y)个

—————————— UPD 2017.2.1 ——————————
今天又看了看这个玩意儿,为什么要$\sqrt n$分块QwQ
暴力不也这复杂度吗……

而且完全不知道$\sum\limits_{d|n} {\frac{n}{d} \cdot \mu (d)}$是$\varphi (n)$也完全可以做啊!
根据狄利克雷卷积,可以知道这货是积性函数,然后再推一推发现可以线筛,然后直接做就好啊!

—————————— UPD 2017.7.3 ——————————
我发现自己之前数学好强
现在看这个题已经不会了qwq

【BZOJ 2818】Gcd

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2818
离线版题目:http://paste.ubuntu.com/20184097/

这个题目,很容易想到枚举素数,然后求gcd=1的对数
用莫比乌斯函数+分段来搞的话,好像很常规,时间复杂度O(ln(n)*sqrt(n)+n)
然后就是看到这篇博客,发现可以直接用phi函数搞QAQ,时间复杂度O(ln(n)+n)
因为phi前缀和那里必须用long long搞得实际运行时间比莫比乌斯函数还要慢QAQ
莫比乌斯函数版本:

#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

题目传送门:http://poj.org/problem?id=1284

题目大意:给一个素数(>3),求原根的个数。
相关定理:如果一个数a有原根,则个数为\(\varphi (\varphi (a))\\)
定理证明:我不会QAQ,可以参考:wiki中的性质一栏

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

我一定不会告诉你:其实我只是来水线性递推欧拉函数的QAQ