conclusion_and_proof_in_number_theory
Download:http://oi.cyo.ng/wp-content/uploads/2018/02/conclusion_and_proof_in_number_theory.pdf
Tag: 欧拉函数
【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