欧拉函数白书模板

太弱,还是备个板子吧

int phi[maxn];
void phi_table(int n){
    for(int i=2;i<=n;i++)phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)if(!phi[i]){
        for(int j=i;j<=n;j+=i){
            if(!phi[j])phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}
时间: 06-07

欧拉函数白书模板的相关文章

数论快速入门(同余、扩展欧几里德、中国剩余定理、大素数测定和整数分解、素数三种筛法、欧拉函数以及各种模板)

数学渣渣愉快的玩了一把数论,来总结一下几种常用的算法入门,不过鶸也是刚刚入门, 所以也只是粗略的记录下原理,贴下模板,以及入门题目(感受下模板怎么用的) (PS:文中蓝色字体都可以点进去查看百度原文) 附赠数论入门训练专题:点我打开专题(题目顺序基本正常,用以配套数论入门) 一.同余定理 简单粗暴的说就是:若 a-b == m 那么 a%m == b%m 这个模运算性质一眼看出...直接上入门水题: Reduced ID Numbers 附AC代码(这个也没啥模板....知道就好) #inclu

数论 - 欧拉函数模板题 --- poj 2407 : Relatives

Relatives Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11372   Accepted: 5544 Description Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if ther

hdu2824 The Euler function 筛选法求欧拉函数模板题

//求a , b范围内的所有的欧拉函数 //筛选法求欧拉函数模板题 #include<cstdio> #include<cstring> #include<iostream> using namespace std ; const int maxn = 3000010 ; typedef __int64 ll ; int e[maxn] ; int a ,  b ; void Euler() { int i,j; for (i=1;i<maxn;i++) e[i]

欧拉函数模板

//直接求解欧拉函数int euler(int n){ //返回euler(n)      int res=n,a=n;     for(int i=2;i*i<=a;i++){         if(a%i==0){             res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出              while(a%i==0) a/=i;         }     }     if(a>1) res=res/a*(a-1);     return re

算法模板——单个值欧拉函数

输入N,输出phi(N) 这样的单个值欧拉函数程序一般见于部分数论题,以及有时候求逆元且取模的数不是质数的情况(逆元:A/B=A*Bphi(p)-1 (mod p),一般常见题中p是质数,phi(p)-1=p-2) (Tip:我是来水经验的不解释,不过话说真的好久没写这个了TT) 1 var i:int64; 2 function Eula(x:int64):int64; 3 var res:int64;i:longint; 4 begin 5 res:=x; 6 for i:=2 to tru

算法模板——线性欧拉函数

实现功能:求出1-N的欧拉函数,然后应对若干个询问操作 其实就是个素数判定+欧拉函数性质的二合一 代码如下,我觉得应高不难懂,只要你知道欧拉函数的性质 var i,j,k,l,m,n:longint; a,b:array[0..10000005] of longint; procedure phi; var i,j:longint; begin m:=0;a[1]:=1; for i:=2 to n do begin if a[i]=0 then begin inc(m); b[m]:=i; a

欧拉函数模板及例题整理

欧拉函数定义:小于n且与n互素的数的个数 欧拉函数为积性函数,满足积性函数的性质,即可以通过n的素因子的函数值求得n的欧拉函数值 求值方式有两种,单个判断和打表 代码如下 int phi(int n) { int res=n; for(int i=2;i*i<=n;i++) { if(n%i==0) { res=res-res/i; while(n%i==0) n/=i; } } if(n>1) res=res-res/n; //可能还有大于sqrt(n)的素因子 return res; }

LA 7362 Farey (数学,欧拉函数)

题意:给定一个数 n,问你0<= a <=n, 0 <= b <= n,有多少个不同的最简分数. 析:这是一个欧拉函数题,由于当时背不过模板,又不让看书,我就暴力了一下,竟然AC了,才2s,题目是给了3s,很明显是由前面递推,前面成立的,后面的也成立, 只要判定第 i 个有几个,再加前 i-1 个就好,第 i 个就是判断与第 i 个互质的数有多少,这就是欧拉函数了. 代码如下: 这是欧拉函数的. #pragma comment(linker, "/STACK:102400

算法复习——欧拉函数(poj3090)

题目: Description A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For exa