acm数论之旅--欧拉函数的证明

时间:2021-10-03 23:45:35
随笔 - 20  文章 - 0  评论 - 73

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

代码如下:

acm数论之旅--欧拉函数的证明
 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 }
acm数论之旅--欧拉函数的证明

(phi就是φ的读音)

机智的代码,机智的我(。・`ω´・)

这个的复杂度是O(√n),如果要你求n个数的欧拉函数,复杂度是O(n√n),这也太慢了

有更快的方法

跟埃筛素数差不多

acm数论之旅--欧拉函数的证明
 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 }
acm数论之旅--欧拉函数的证明

(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 }
acm数论之旅--欧拉函数的证明

最后说下

a^b % p  不等价  (a%p)^(b%p) % p

因为

a^φ(p) ≡ 1 (mod p)

所以

a^b % p  =  (a%p)^(b%φ(p)) % p

(欧拉函数前提是a和p互质)

acm数论之旅--欧拉函数的证明

如果p是质数

直接用这个公式

acm数论之旅--欧拉函数的证明

机智的代码,机智的我(。・`ω´・)

///////////////////////////////////////////////

2016年7月23号

我的天哪,我又发现了一个新公式,貌似可以摆脱a和p互质的束缚,让我们来命名为:超欧拉取模进化公式

a^b = a^( b % phi(m) + phi(m) ) ( mod m ),这个公式的前提条件是 b >= phi(m)

这是历史性的一刻,妈妈再也不用为a和p不互质而担心了= =

Huge Mods

UVA - 10692

#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数论之旅--欧拉函数的证明的更多相关文章

  1. ACM数论之旅7---欧拉函数的证明及代码实现(我会证明都是骗人的╮&lpar; ̄&bigtriangledown; ̄&rpar;╭)

    欧拉函数,用φ(n)表示 欧拉函数是求小于等于n的数中与n互质的数的数目 辣么,怎么求哩?~(-o ̄▽ ̄)-o 可以先在1到n-1中找到与n不互质的数,然后把他们减掉 比如φ(12) 把12质因数分解 ...

  2. 陕西师范大学第七届程序设计竞赛网络同步赛 J 黑猫的小老弟【数论&sol;法拉数列&sol;欧拉函数】

    链接:https://www.nowcoder.com/acm/contest/121/J来源:牛客网 题目描述 大家知道,黑猫有很多的迷弟迷妹,当然也有相亲相爱的基友,这其中就有一些二五仔是黑猫的小 ...

  3. 1370 - Bi-shoe and Phi-shoe&lpar;LightOJ1370&rpar;&lpar;数论基础,欧拉函数&rpar;

    http://lightoj.com/volume_showproblem.php?problem=1370 欧拉函数: 在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目. φ(n) ...

  4. 【bzoj3813】&colon; 奇数国 数论-线段树-欧拉函数

    [bzoj3813]: 奇数国 题意:给定一个序列,每个元素可以分解为最小的60个素数的形式.(x=p1^k1*p2^k2*......p60^k60)(p1=2,p2=3,…,p60=281) 支持 ...

  5. 【数论】【欧拉函数】CDOJ1724 为了我们心爱的京电

    京州电子科技大学遭遇废校危机,为了保护我们心爱的学校,N位魔法少女站了出来,她们能做的就是……成为偶像! 每个魔法少女都拥有一定的人气,他们中的每个人的人气计算方式如下: 假设某个魔法少女的学号为a, ...

  6. 【数论】【欧拉函数】【筛法求素数】【乘法逆元】【快速幂取模】bzoj2186 &lbrack;Sdoi2008&rsqb;沙拉公主的困惑

    http://www.cnblogs.com/BLADEVIL/p/3490321.html http://www.cnblogs.com/zyfzyf/p/3997986.html 翻了翻题解,这两 ...

  7. 【数论】【欧拉函数】bzoj2190 &lbrack;SDOI2008&rsqb;仪仗队

    由图可知,一个人无法被看到时,当且仅当有 人与原点 的斜率与他相同,且在他之前. ∴一个人可以被看到,设其斜率为y/x,当且仅当y/x不可再约分,即gcd(x,y)=1. 考虑将图按对角线划分开,两部 ...

  8. UVA 12493 Stars &lpar;欧拉函数--求1~n与n互质的个数)

    pid=26358">https://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&cate ...

  9. 数学之欧拉函数 &amp&semi;几道poj欧拉题

    欧拉函数总结+证明 欧拉函数总结2 POJ 1284 原根 #include<iostream> #include<cstdio> #include<cstring&gt ...

随机推荐

  1. mac个人设置

    修改spotlight快捷键 mac默认的command+space和我windows下的习惯冲突,修改为ctrl+space 删除输入法切换的快捷键 因为我不需要切换不同语言的快捷键.中英文切换直接 ...

  2. Win7下共享WiFi热点方法

    管理员权限运行CMD netsh wlan set hostednetwork mode=allow ssid=Wifi名称 key=Wifi密码 netsh wlan start hostednet ...

  3. Codrops 教程:实现内容倾斜的 3D 幻灯片效果

    今天给大家分享的优秀教程来自 Codrops 网站,实现一个内容倾斜的 3D 幻灯片效果.我们平常见到的都是那种水平或者垂直滚动的效果,这个倾斜的内容滑动效果相信会让你眼前一亮.因为使用了 CSS 3 ...

  4. EChart 关于图标控件的简单实用

    1.下载前段框架并放入项目中去. 2.在js中调用 <!DOCTYPE html> <html lang="en"> <head> <me ...

  5. nav

    $(document).ready(function() { $(window).resize(function(){ var need=0; var ul_max_width = $(window) ...

  6. EF 已有打开的与此 Command 相关联的 DataReader,必须首先将它关闭

    在以下代码中,当第二次foreach时会抛出该异常,原因是:由于Entity在读取数据的时候使用的是DbDataReader进行读取,当作为IEnumuerable<T>对象MoveNex ...

  7. CGBitmapContextCreate函数

    CGBitmapContextCreate函数参数详解 函数原型: CGContextRef CGBitmapContextCreate ( void *data,    size_t width, ...

  8. Android自己定义组件系列【2】——Scroller类

    在上一篇中介绍了View类的scrollTo和scrollBy两个方法,对这两个方法不太了解的朋友能够先看<自己定义View及ViewGroup> scrollTo和scrollBy尽管实 ...

  9. &lt&semi;密码的实现&gt&semi;输入密码的时候,显示&OpenCurlyDoubleQuote;&ast;”,而不是显示输入内容

    一开始还以为用C语言和C++不能实现输入密码的时候显示出“*”而不显示输入的内容呢!没想到偶然的机会试出了用while循环结构可以实现.以下是我整理的C语言和C++的代码,供初学者参考. 这是C语言实 ...

  10. C&num;做一个写txt文件流的测试&comma;为什么配置低的机器写入的还快

    测试机:笔记本i7 8G 固态硬盘 由于采取读码写入txt方式, 读码频率挺高,文件名为日期格式,当前采用每次读码打开文件写入的方式, 为什么没用sb,因为怕断电情况的数据丢失.所以采取每条存入的方式 ...