#include<cstdio> #define MAX 1000000 int phi[MAX+10],pri[MAX+10],cnt=0; bool f[MAX+10]; void getphi()//欧拉筛筛素数和phi值  { phi[1]=1; for(int i=2;i<=MAX;i++) { if(!f[i]) { pri[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt&&i*pri[j]<=MAX;j++)...

#include<iostream> #include<cstdio> #include<cmath> #define ll long long using namespace std; ll gcd(ll a,ll b)//求最大公约数  { int t; while((a%=b)!=0){ t=a,a=b,b=t; } return b; } ll multiply(ll x, ll y,ll p...

#include <stdio.h> int main() { while(1) printf("我是废物");  return 0;  } 

#include <bits/stdc++.h> using namespace std; typedef long long ll; int Get_phi(int n) { int phi=n; for(int i=2;(ll)i*i<=n;++i) { if(n%i==0) { phi=(ll)phi*(i-1)/i; while(n%i==0) n/=i;  } } if(n>1) phi=(ll)phi*(n-1)/n; ...

#include <bits/stdc++.h> using namespace std; typedef long long ll;  ll gcd(ll a,ll m)//辗转相除法求最大公约数  { ll b; while(m%a){ m%=a; b=m,m=a,a=b; } return a; } ll Get_phi(ll n)//欧拉定义法求phi(n)  { ll phi=n; for(ll&nbsp...

#include <bits/stdc++.h> using namespace std; #define MAXN 10000000 bool f[MAXN+10]; int phi[MAXN+10],pri[MAXN+10],n,cnt; void Get_phi(){//欧拉筛筛出范围内的所有phi值  phi[1]=1; for(int i=2;i<=MAXN;i++) { if(!f[i]){  pri[++cnt]=i;//保存质数  phi[i...

/*根据三条性质推导即可。 线性筛中每一个数字最多只会被筛一次，因此正好可以对每一个数字求欧拉函数。 线性筛正好是由小的数字筛到大的数字 or 正好是指数 前者用后两条性质 后者用第一条性质即可。 三条性质如下：  1.如果n为某一素数的幂次，那么: φ(p^a)=(p-1)*p^(a-1)  (φ(p)=p-1)  2.如果i mod p=0,那么φ(i*p)=p*φ(i)  3.如果i mod p≠0，那么φ(i*p)=φ(i)*(p-1)*/ #include <bits/stdc++.h> using namesp...

#include <bits/stdc++.h>//万能头文件  using namespace std;//链接头文件  int read()//快速读取，节约时间  { int m=0,n=0; char ch=getchar(); while(!isdigit(ch)) {//isdigit为判断读入的字符是否为数字  if(ch=='-') m=1; ch=getchar(); } while(isdigit(ch)){ n=(n<<3)+(n...

//关于freopen的stdin和stdout的使用 //加快输入和输出速度 #include <stdio.h> int main() {  #ifndef ONLINE_JUDGE//起始（online_judge在线测评系统） freopen("4139.txt","r",stdin); freopen("self.txt","w",stdout); #endif//结束  int n,m; char a[20]="Hello,world!"; scanf("%d%d",&n,&m); p...

#include <stdio.h> int a,ch='9'; void _1()//&的测试  {   for(int j=0;j<20;j++) { printf("%d&i(i从0~19):",j); for(int i=0;i<20;i++){ if(i&j) printf("%d ",i);//一般的运用有：(a&1)->等同于a%2==1（但更快）其他的用法，看运行结果探索规律吧（用八位二进制找原理）  } printf...

int ：     粗范围：-1e+9 ~ 1e+9  （10^9以内）     具体范围：-2147483648 ~ 2147483647（-pow(2,31)-1 ~ pow(2,31)）        long long ：     粗范围：-1e+18 ~ 1e+18  （10^18以内）     具体范围：-pow(2,63) ~ pow(2,63)-1    float, double ,long double：   使用顺序 float > double > long double（一般|1e+10|以内用f...

#include <stdio.h> int qpow(int b, int e,int s)//快速幂 {     int a = 1,c;     for(int i=e;i;i>>=1)//简化计算次数将1，2，3，4……变成2^1，2^2，2^3，2^4……     {         if(i&1) a=(long long)a * b % s;      &nbs...

#include <stdio.h> int main() { int N,num=0; scanf("%d",&N); if(N==1) printf("%d\n",N-1); if(N==2) printf("%d\n",N+1); if(N>=3&&N<=40000) { int m=N-1; while(m>=1) { int ans=m; N=m; for(int i=2;i*i<=N;i++) { if(N%i==0)  { ans*...

//基于欧拉公式对欧拉函数代码进行优化  #include <stdio.h> int main() { int ans,n; scanf("%d",&n); ans=n; for(int i=2;i*i<=n;i++)//查找  { if(n%i==0) { ans*=(i-1.0)/i;//定义公式  while(n%i==0)  n/=i*1.0;//找出n的因数中与i互质的最大因数  } } if(n>1) ans*=(n-1)*1.0/n;//补充for...