首页 > 代码库 > BZOJ1968: [Ahoi2005]COMMON 约数研究

BZOJ1968: [Ahoi2005]COMMON 约数研究

2024-07-16 17:53:10   220人阅读

1968: [Ahoi2005]COMMON 约数研究

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 919  Solved: 681
[Submit][Status]

Description

Input

只有一行一个整数 N（0 < N < 1000000）。

Output

只有一行输出，为整数M，即f(1)到f(N)的累加和。

Sample Input

3

Sample Output

5

HINT

 

Source

Day2

题解：
一开始写了个线性筛+dfs，忽然发现时限根本不够用，而且跑极限数据忒慢
一看status觉得不对劲，怎么代码都这么短？肯定有什么我没学过的高大上的结论。。。
一百度：考虑每个数对总体的贡献……在1-n所有数中，i一共可以成为n/i个数的约数，也即所有的约数中有n/i个i，所以扫一遍累加答案就好了。
卧槽！一秒变水题！
我竟然还想到了约数个数公式，难道想的太多了囧。。。
这也算是逆向思维吧。
代码：
1.。。。
1 var i,n,ans:longint;2 begin3   assign(input,‘input.txt‘);assign(output,‘output.txt‘);4   reset(input);rewrite(output);5   readln(n);6   for i:=1 to n do inc(ans,n div i);7   writeln(ans);8   close(input);close(output);9 end.
View Code

2.正解

 1 const maxn=1000000+1000; 2 var ans:int64; 3     f,p:array[0..maxn] of int64; 4     check:array[0..maxn] of boolean; 5     i,n,tot:longint; 6 procedure getprimes; 7  var i,j,k:longint; 8  begin 9    fillchar(check,sizeof(check),false);10    for i:=2 to n do11     begin12       if not(check[i]) then begin inc(tot);p[tot]:=i;end;13       for j:=1 to tot do14        begin15          k:=i*p[j];16          if k>n then break;17          check[k]:=true;18          if i mod p[j]=0 then break;19        end;20     end;21  end;22 procedure dfs(x,pos:int64);23  var y:int64;i:longint;24  begin25    if pos>tot then exit;26    y:=x;dfs(x,pos+1);27    for i:=1 to 22 do28     begin29      y:=y*p[pos];if y>n then break;30      f[y]:=f[x]*(i+1);31      dfs(y,pos+1);32     end;33  end;34 35 procedure main;36  begin37    getprimes;38    f[1]:=1;39    dfs(1,1);40    ans:=1;41    for i:=2 to n do inc(ans,f[i]);42    writeln(ans);43  end;44 45 begin46   assign(input,‘input.txt‘);assign(output,‘output2.txt‘);47   reset(input);rewrite(output);48   readln(n);49   main;50   close(input);close(output);51 end.
View Code

 


联系
我们