数论 欧拉函数 欧拉定理 扩展欧拉定理
最近紧急恶补数论..
公式性质总结：
三个欧拉函数线性筛公式：
]
]
]
通项公式:
]
欧拉定理：
]
扩展欧拉定理：
欧拉函数
在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目。规定：(varphi(1)=1)
求解欧拉函数：
方法一：
欧拉函数的通项公式：
]
欧拉函数通项公式的证明，从别人的博客偷过来的：
代码：
ll oula(ll k){
ll ans=k;
for(ll i=2;i*i<=k;++i){
if(k%i==0) ans-=ans/i;
while(k%i==0) k/=i;
}
if(k>1) ans-=ans/k;
return ans;
}
方法二：
线性求欧拉函数
预备性质：
以下的p为质数
]
性质一：这个好解释，因为p为质数，所以1~p-1的每一个数都和p互质
]
性质二：根据欧拉函数的积性？。。
]
性质三：。。<(￣ c￣)y▂ξ
然后将这三条性质代入欧拉筛即可
for(int i=2;i<=10000000;++i){
if(!vis[i]){
phi[i]=i-1; //性质一
prime[++prime[0]]=i;
}
for(int j=1;j<=prime[0]&&prime[j]*i<=10000000;++j){
vis[prime[j]*i]=true;
if(i%prime[j]!=0)
phi[prime[j]*i]=phi[prime[j]]*phi[i]; //性质二
else{
phi[prime[j]*i]=prime[j]*phi[i]; //性质三
break;
}
}
}
至此，是欧拉函数的两种求法。两种方法各有优势，无法相互取代
欧拉定理
欧拉定理：
]
不会证明，但人家好背嘛ˋ( ° ▽、° )
回顾一下费马小定理：
]
同时，众所周知的是：
]
┌(。Д。)┐现在从欧拉定理看费马小定理，有没有看儿子的感觉
扩展欧拉定理
扩展欧拉定理：
证明什么的自然是不会的..(/▽＼)
例题
上帝与集合的正确用法
一句话题干：
乍一眼看上去好似误解，事实上我就是佩服出题人脑洞套用扩展欧拉定理之后，发现是可解的
设f(n)为模数为n时的答案，(zeta)为那一坨无限平方
]
]
]
]
递归的边界易知：
]
解决（￣︶￣）↗
Please, another Queries on Array?
CF1114F Please, another Queries on Array?
简述题干:
维护一个数列支持以下操作
-
为区间[l,r]乘上一个正整数
-
求区间乘积的欧拉函数
codeforce的出题人脑洞大出天际
单看操作一，只需要简单的线段树就可以实现
再看操作二..这，wtf?!
利用一下欧拉函数的通项公式：
]
由于题干的限制，不论是初始数组，还是后来乘上来的数字，其大小不会大于300，也就是说其质因数不会大于300。不大于300的质因数只有62个！
根据公式，我们需要知道：区间乘积和区间质因数情况，对于区间乘积，用long long存储，过程中不断用模数取余即可；对于区间质因数个数，用一个long long状压一下62个质因数的出现情况，由于只增不减的条件，数据变得很好处理。
ok，这就是亏我理解了，还是调了两个小时的题。。
原文链接: https://www.cnblogs.com/ticmis/p/13210772.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/360486
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
