ACM数论之旅7---欧拉函数的证明及代码实现(我会证明都是骗人的╮( ̄▽ ̄)╭)
欧拉函数,用φ(n)表示
欧拉函数是求小于等于n的数中与n互质的数的数目
辣么,怎么求哩?~(~o ̄▽ ̄)~o
可以先在1到n-1中找到与n不互质的数,然后把他们减掉
比如φ(12)
把12质因数分解,12=2*2*3,其实就是得到了2和3两个质因数
然后把2的倍数和3的倍数都删掉
2的倍数:2,4,6,8,10,12
3的倍数:3,6,9,12
本来想直接用12 - 12/2 - 12/3
但是6和12重复减了
所以还要把即是2的倍数又是3的倍数的数加回来 (>﹏<)
所以这样写12 - 12/2 - 12/3 + 12/(2*3)
这叫什么,这叫容斥啊,容斥定理听过吧
比如φ(30),30 = 2*3*5
所以φ(30) = 30 - 30/2 - 30/3 - 30/5 + 30/(2*3) + 30/(2*5) + 30/(3*5) - 30/(2*3*5)
但是容斥写起来好麻烦( ̄. ̄)
有一种简单的方法
φ(12) = 12*(1 - 1/2)*(1 - 1/3) = 12*(1 - 1/2 - 1/3 + 1/6)
φ(30) = 30*(1 - 1/2)*(1 - 1/3)*(1 - 1/5) = 30*(1 - 1/2 - 1/3 - 1/5 + 1/6 + 1/10 + 1/15 - 1/30)
你看( •̀∀•́ ),拆开后发现它帮你自动帮你容斥好
所以φ(30)的计算方法就是先找30的质因数
分别是2,3,5
然后用30* 1/2 * 2/3 * 4/5就搞定了
顺便一提,phi(1) = 1
代码如下:
1 //欧拉函数
2 int phi(int x){
3 int ans = x;
4 for(int i = 2; i*i <= x; i++){
5 if(x % i == 0){
6 ans = ans / i * (i-1);
7 while(x % i == 0) x /= i;
8 }
9 }
10 if(x > 1) ans = ans / x * (x-1);
11 return ans;
12 }
(phi就是φ的读音)
机智的代码,机智的我(。・`ω´・)
这个的复杂度是O(√n),如果要你求n个数的欧拉函数,复杂度是O(n√n),这也太慢了
有更快的方法
跟埃筛素数差不多
1 #include<cstdio>
2 const int N = 100000 + 5;
3 int phi[N];
4 void Euler(){
5 phi[1] = 1;
6 for(int i = 2; i < N; i ++){
7 if(!phi[i]){
8 for(int j = i; j < N; j += i){
9 if(!phi[j]) phi[j] = j;
10 phi[j] = phi[j] / i * (i-1);
11 }
12 }
13 }
14 }
15 int main(){
16 Euler();
17 }
(Euler就是欧拉)
另一种,比上面更快的方法
需要用到如下性质
p为质数
1. phi(p)=p-1 因为质数p除了1以外的因数只有p,故1至p的整数只有p与p不互质
2. 如果i mod p = 0, 那么 phi(i * p)=phi(i) * p (我不会证明)
3.若i mod p ≠0, 那么 phi( i * p )=phi(i) * ( p-1 ) (我不会证明)
(所以我说我会证明都是骗人的╮( ̄▽ ̄)╭)
代码如下:
2 using namespace std;
3 const int N = 1e6+10 ;
4 int phi[N], prime[N];
5 int tot;//tot计数,表示prime[N]中有多少质数
6 void Euler(){
7 phi[1] = 1;
8 for(int i = 2; i < N; i ++){
9 if(!phi[i]){
10 phi[i] = i-1;
11 prime[tot ++] = i;
12 }
13 for(int j = 0; j < tot && 1ll*i*prime[j] < N; j ++){
14 if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j]-1);
15 else{
16 phi[i * prime[j] ] = phi[i] * prime[j];
17 break;
18 }
19 }
20 }
21 }
22
23 int main(){
24 Euler();//先初始化为零
25 }
最后说下
a^b % p 不等价 (a%p)^(b%p) % p
因为
a^φ(p) ≡ 1 (mod p)
所以
a^b % p = (a%p)^(b%φ(p)) % p
(欧拉函数前提是a和p互质)
如果p是质数
直接用这个公式
机智的代码,机智的我(。・`ω´・)
///////////////////////////////////////////////
2016年7月23号
我的天哪,我又发现了一个新公式,貌似可以摆脱a和p互质的束缚,让我们来命名为:超欧拉取模进化公式
a^b = a^( b % phi(m) + phi(m) ) ( mod m ),这个公式的前提条件是 b >= phi(m)
这是历史性的一刻,妈妈再也不用为a和p不互质而担心了= =
Huge Mods
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std;
typedef long long ll;
const int maxm = 1e4 + ;
int m, n;
char ch[];
int a[], phi[maxm];
void Euler(){
phi[] = ;
for(int i = ; i < maxm; i ++){
if(!phi[i]){
for(int j = i; j < maxm; j += i){
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i-);
}
}
}
}
int qpow(int x, int b, int mod) {
int res = ;
while (b > ) {
if (b & ) {
res = res * x % mod;
}
x = x * x % mod;
b >>= ;
}
return res;
}
int solve(int d, int m) {
if(d == n - ) return a[d] % m;
int x = phi[m] + solve(d + , phi[m]);
//关键,主要是除phi[m].
return qpow(a[d], x, m) % m;
}
int t;
int main() {
Euler();
while(~scanf("%s", ch)) {
if(ch[] == '#') break;
sscanf(ch, "%d", &m);
scanf("%d", &n);
for(int i = ; i < n; i++) {
scanf("%d", &a[i]);
}
// if(n == 1) printf("Case #%d: %d\n", ++t, n );
// else
printf("Case #%d: %d\n", ++t, solve(, m));
}
return ;
}
acm数论之旅--欧拉函数的证明的更多相关文章
-
ACM数论之旅7---欧拉函数的证明及代码实现(我会证明都是骗人的╮( ̄▽ ̄)╭)
欧拉函数,用φ(n)表示 欧拉函数是求小于等于n的数中与n互质的数的数目 辣么,怎么求哩?~(-o ̄▽ ̄)-o 可以先在1到n-1中找到与n不互质的数,然后把他们减掉 比如φ(12) 把12质因数分解 ...
-
陕西师范大学第七届程序设计竞赛网络同步赛 J 黑猫的小老弟【数论/法拉数列/欧拉函数】
链接:https://www.nowcoder.com/acm/contest/121/J来源:牛客网 题目描述 大家知道,黑猫有很多的迷弟迷妹,当然也有相亲相爱的基友,这其中就有一些二五仔是黑猫的小 ...
-
1370 - Bi-shoe and Phi-shoe(LightOJ1370)(数论基础,欧拉函数)
http://lightoj.com/volume_showproblem.php?problem=1370 欧拉函数: 在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目. φ(n) ...
-
【bzoj3813】: 奇数国 数论-线段树-欧拉函数
[bzoj3813]: 奇数国 题意:给定一个序列,每个元素可以分解为最小的60个素数的形式.(x=p1^k1*p2^k2*......p60^k60)(p1=2,p2=3,…,p60=281) 支持 ...
-
【数论】【欧拉函数】CDOJ1724 为了我们心爱的京电
京州电子科技大学遭遇废校危机,为了保护我们心爱的学校,N位魔法少女站了出来,她们能做的就是……成为偶像! 每个魔法少女都拥有一定的人气,他们中的每个人的人气计算方式如下: 假设某个魔法少女的学号为a, ...
-
【数论】【欧拉函数】【筛法求素数】【乘法逆元】【快速幂取模】bzoj2186 [Sdoi2008]沙拉公主的困惑
http://www.cnblogs.com/BLADEVIL/p/3490321.html http://www.cnblogs.com/zyfzyf/p/3997986.html 翻了翻题解,这两 ...
-
【数论】【欧拉函数】bzoj2190 [SDOI2008]仪仗队
由图可知,一个人无法被看到时,当且仅当有 人与原点 的斜率与他相同,且在他之前. ∴一个人可以被看到,设其斜率为y/x,当且仅当y/x不可再约分,即gcd(x,y)=1. 考虑将图按对角线划分开,两部 ...
-
UVA 12493 Stars (欧拉函数--求1~n与n互质的个数)
pid=26358">https://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&cate ...
-
数学之欧拉函数 &;几道poj欧拉题
欧拉函数总结+证明 欧拉函数总结2 POJ 1284 原根 #include<iostream> #include<cstdio> #include<cstring> ...
随机推荐
-
mac个人设置
修改spotlight快捷键 mac默认的command+space和我windows下的习惯冲突,修改为ctrl+space 删除输入法切换的快捷键 因为我不需要切换不同语言的快捷键.中英文切换直接 ...
-
Win7下共享WiFi热点方法
管理员权限运行CMD netsh wlan set hostednetwork mode=allow ssid=Wifi名称 key=Wifi密码 netsh wlan start hostednet ...
-
Codrops 教程:实现内容倾斜的 3D 幻灯片效果
今天给大家分享的优秀教程来自 Codrops 网站,实现一个内容倾斜的 3D 幻灯片效果.我们平常见到的都是那种水平或者垂直滚动的效果,这个倾斜的内容滑动效果相信会让你眼前一亮.因为使用了 CSS 3 ...
-
EChart 关于图标控件的简单实用
1.下载前段框架并放入项目中去. 2.在js中调用 <!DOCTYPE html> <html lang="en"> <head> <me ...
-
nav
$(document).ready(function() { $(window).resize(function(){ var need=0; var ul_max_width = $(window) ...
-
EF 已有打开的与此 Command 相关联的 DataReader,必须首先将它关闭
在以下代码中,当第二次foreach时会抛出该异常,原因是:由于Entity在读取数据的时候使用的是DbDataReader进行读取,当作为IEnumuerable<T>对象MoveNex ...
-
CGBitmapContextCreate函数
CGBitmapContextCreate函数参数详解 函数原型: CGContextRef CGBitmapContextCreate ( void *data, size_t width, ...
-
Android自己定义组件系列【2】——Scroller类
在上一篇中介绍了View类的scrollTo和scrollBy两个方法,对这两个方法不太了解的朋友能够先看<自己定义View及ViewGroup> scrollTo和scrollBy尽管实 ...
-
<;密码的实现>;输入密码的时候,显示“*”,而不是显示输入内容
一开始还以为用C语言和C++不能实现输入密码的时候显示出“*”而不显示输入的内容呢!没想到偶然的机会试出了用while循环结构可以实现.以下是我整理的C语言和C++的代码,供初学者参考. 这是C语言实 ...
-
C#做一个写txt文件流的测试,为什么配置低的机器写入的还快
测试机:笔记本i7 8G 固态硬盘 由于采取读码写入txt方式, 读码频率挺高,文件名为日期格式,当前采用每次读码打开文件写入的方式, 为什么没用sb,因为怕断电情况的数据丢失.所以采取每条存入的方式 ...