今天依旧是讲数论。我觉得我这两天没太大的收获，至少写代码的能力没啥长进。数论大部分是和数学有关的，理解起来困难，转化为程序理解更难。我都是老师解释的大部分能听懂，一变为程序就一脸懵逼。所以那些求……的模板都是死记硬背的。昨天讲的是进制，回文数，整除一些的。今天讲的是各种定理的解释和代码。
今天讲了两个求素数的方法：埃式筛法和线性筛法。
const int maxn=100000;//埃式筛法bool isprime[maxn];void searchPrime(int n){ memset(isprime,true,sizeof(isprime));//=isprime[maxn]={1} isprime[1]=false; for(i=2;i<=n;i++) if(isprime(i)) { j=i*i; while(j<=maxn) { isprime[j]=false; j+=i; } }}
void seive(int Max)//线性筛法{ memset(isPrime,true,sizeof(isPrime)); isPrime[0]=false; isPrime[1]=false; for(int i=2;i<=Max;i++)//遍历筛去所有最大因数是i的合数 { if(isPrime[i]) prime[++total]=i;//把素数记录下来 //遍历已知素数表中比i的最小素因数小的素数，并筛去合数 for(int j=1;j<=total&&i*prime[j]<=Max;j++) { isPrime[i*prime[j]]=false; if((i%prime[j])==0) break;//找到i的最小素因数 } }}
这些模板算法我都理解不全。尽管有比较详尽的注释说明，但依旧不太明白，这些模板还要默写所以我都死记硬背背下来。还有一个欧拉函数这比前两个素数的什么筛法还要难理解。
#include<bits/stdc++.h>using namespace std;int main(){ int k=2,s=n;//求欧拉函数(n) while(k*k<=n) { if(n%k==0) { s=s*(k-1)/k; while(n%k==0) n/=k; } k++; } if(n>1) s*=(n-1)/n; cout<<s;}
for(int i=2;i<=n;i++)//求欧拉函数(i),i=1~n{ if(!IsPrime[i]) { prime[++cnt]=i; phi[i]=i-1; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n) break; Isprime[prime[j]*i]=1; if (i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } //i含prime[j]因子 else phi[i*prime[j]]=phi[i]*(prime[j]-1); //i不含prime[j]因子 }}
上面是这一天较重要的几段程序。下面是没那么重要但也很常用的模板
k=2;//n的质因数分解while (k*k<=a){ if(a%k==0) while(a%k==0) { a/=k; …//对因子重数的其他处理 } k++;}if (a>1) …//再对分解最后的那个质数进行处理
int nums(int n)//求n的约数个数{ int k, res, p; k=2; res=1; while (k*k<=a) { p=1; while (n%k==0) { a/=k; p++; } res*=p; k++; } if(a>1) res*=2;//只剩一个最大的质因子 return res;}
int sum(int n)//求n的约数和{ int k, res, tmp; k=2; res=1; while (k*k<=a) { tmp=1; while (n%k==0) { a/=k; tmp=tmp*k+1; } res*=tmp; k++; } if (a>1) res*=(1+a);//只剩一个最大的质因子 return res;}
今天的收获大概就是这些还未理解的几个模板吧
