创建网站的过程,网站怎么解析到域名,wordpress2012主题二次开发,浙江网站建设推广参考博客 参考博客 参考博客
这个讲的挺好 预备知识点#xff1a; 大于1的数n可以分解质因数#xff1a; np1a1p2a2p3a3*…*pka n的约数的个数是(a11) * (a21) * (a31)…(ak1) 我们先用线性筛来筛出素数
bool mark[maxn];
int prim[maxn];
int cnt;
void initial()
{cnt0;f…参考博客 参考博客 参考博客
这个讲的挺好 预备知识点 大于1的数n可以分解质因数 np1a1×p2a2×p3a3*…*pka n的约数的个数是(a11) * (a21) * (a31)…(ak1) 我们先用线性筛来筛出素数
bool mark[maxn];
int prim[maxn];
int cnt;
void initial()
{cnt0;for (int i2 ; iN ; i){if (!mark[i])prim[cnt]i;//存放素数for (int j0 ; jcnt i*prim[j]N ; j){mark[i*prim[j]]1;//标记为素数if (!(i%prim[j]))break;}}
}求约数个数
n的约数的个数是(a11) * (a21) * (a31)…(ak1) 我们可以用线性筛筛出当前n的约数个数 证明 d[i]表示i的约数的个数 num[i]表示i的最小素因子的个数 prim[i]表示第i个素数 分下列情况
i为质数 因为i为质数所以素因子只有本身且指数为1 所以num[i]1,d[i]2(1和本身)i%prim[j]!0 说明i不包含prim[j]这个素因子但是i*prim[j]包含一个素因子prim[j]所以 d(i∗prime[j])(1r1)∗……∗(1rk)∗(11)d[i] * d[prim[j]] d[i] * 2 而且因为我们是从小到大枚举所以当前的prim[j]必然是i * prim[j]的最小素因子所以num[i * prim[j]] 1i%prim[j] 0 i中包含prim[j]且为i的最小素因子 d(i∗prime[j])(1r11)∗……∗(1rk) d(i∗prime[j])d(i)/(num(i)1)∗(num(i)2) num(i∗prime[j])num(i)1
#include iostream
#include cstdio
#include cstringusing namespace std;const int wx1017;int isprime[wx],prime[wx],d[wx],num[wx];
int tot,n,m;inline int read(){int sum0,f1; char chgetchar();while(ch0||ch9){if(ch-)f-1; chgetchar();}while(ch0ch9){sum(sum1)(sum3)ch-0; chgetchar();}return sum*f;
}void Euler(){memset(isprime,1,sizeof isprime); d[1]1;for(int i2;in;i){if(isprime[i]){prime[tot]i;d[i]2;num[i]1;}for(int j1;jtoti*prime[j]n;j){isprime[i*prime[j]]0;if(i%prime[j]0){d[i*prime[j]]d[i]/(num[i]1)*(num[i]2);num[i*prime[j]]num[i]1; break;}else{d[i*prime[j]]d[i]*2;num[i*prime[j]]1;}}}
}int main(){nread(); Euler();for(int i1;in;i)printf(%d %d\n,i,d[i]);return 0;
}线性筛约数和
我们用sd(i)表示i的约数和 根据算数基本定理 sd(n)(1p1p21……pr11)∗(1p2p22……pr22)∗……∗(1pkp2k……prkk) 最小质因子的那一项是(1p1p21……pr11) 我们用num[i]来表示最小质因子的那一项 证明 和上面一样分类讨论
i为素数 sd(i)i1num(i)i1i%prim[j] ! 0 i∗prime[j]里原先没有prime[j]这一项加上后 sd(i∗prime[j])sd(i)∗sd(prime[j]) num(i∗prime[j])1prime[j] 大体思路如上i%prim[j] 0 d(i∗prime[j])(d(i)/num(i)∗(num(i)∗prime[j])1 num(i∗prime[j])num(i)∗prime[j]1
代码
#include iostream
#include cstdio
#include cstringusing namespace std;const int wx1017; inline int read(){int sum0,f1; char chgetchar();while(ch0||ch9){if(ch-)f-1; chgetchar();}while(ch0ch9){sum(sum1)(sum3)ch-0; chgetchar();}return sum*f;
}int isprime[wx],sd[wx],num[wx],prime[wx];
int n,tot;void Euler(){memset(isprime,1,sizeof isprime); sd[1]1;for(int i2;in;i){if(isprime[i]){prime[tot]i;sd[i]1i; num[i]1i;}for(int j1;jtotprime[j]*in;j){isprime[i*prime[j]]0;if(i%prime[j]!0){sd[i*prime[j]]sd[i]*sd[prime[j]];num[i*prime[j]]prime[j]1;}else{sd[i*prime[j]]sd[i]/num[i]*(num[i]*prime[j]1);num[i*prime[j]]num[i]*prime[j]1; break;}}}
}int main(){nread(); Euler();for(int i1;in;i)printf(%d %d\n,i,sd[i]);return 0;
}
