1968: [Ahoi2005]COMMON 約數(shù)研究

Description

Input

只有一行一個(gè)整數(shù) N（0 < N < 1000000）。

Output

只有一行輸出，為整數(shù)M，即f(1)到f(N)的累加和。

Sample Input

3

Sample Output

5

---

　　這一定是一道水題，當(dāng)時(shí)因?yàn)檫@是練習(xí)積性函數(shù)的“好機(jī)會(huì)”，結(jié)果發(fā)現(xiàn)自己實(shí)在想得太復(fù)雜。0 < N < 1000000，因數(shù)不會(huì)超過(guò)這個(gè)界限，那么跑一遍就完了。代碼也不用掛了。（52ms）

　　但我發(fā)現(xiàn)，也可以歐拉篩。（288 ms）

　　當(dāng)然，還可使用區(qū)間亂跳，O（1）算出n div i為一定值的區(qū)間，而這種區(qū)間是O（sqrt(n)）的。（0 ms）

?

1 /************************************************************** 2 Problem: 1968 3 User: Doggu 4 Language: C++ 5 Result: Accepted 6 Time:288 ms 7 Memory:13516 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 const int SIZE= 1000000; 12 int prime[SIZE], pri, n; 13 bool vis[SIZE+10]; 14 long long ans, tao[SIZE+10]; 15 void EULER(int upper_bound) { 16 tao[1]=1; 17 for( long long i = 2; i <= upper_bound; i++ ) { 18 if(!vis[i]) { 19 prime[++pri]=i; 20 tao[i]=2; 21 } 22 for( int t = 1; t <= pri; t++ ) { 23 long long j = i*prime[t]; 24 if(j>upper_bound) break; 25 vis[j]=1; 26 tao[j]=tao[i]*tao[prime[t]]; 27 if(i%prime[t]==0) { 28 long long a = i,tot=0; 29 while(a%prime[t]==0) a/=prime[t],tot++; 30 tao[j]=tao[a]*(tot+2); 31 break; 32 } 33 } 34 } 35 } 36 int main() { 37 scanf("%d",&n); 38 EULER(n+10); 39 for( int i = 1; i <= n; i++ ) ans+=tao[i]; 40 printf("%lld\n",ans); 41 return 0; 42 } EULER

?

?

?

?

?

?

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/Doggu/p/bzoj1968.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1968 [Ahoi2005]COMMON 约数研究的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。