UVA 11426 欧拉函数 + 递推

2019-11-06 07:32:59

字体：大中小

来源：转载

供稿：网友

code

import java.util.*;import static java.lang.System.*;public class Main{ static final int N = 4100000; /**static long c;*/ static long[] phi = new long[N]; static long[] f = new long[N]; static long[] s = new long[N]; public static void main(String[] args){ Scanner in = new Scanner(System.in); init(); while(in.hasNext()){ int n = in.nextInt(); if(n == 0) break; out.PRintln(s[n]); } in.close(); } public static void init(){ for(int i = 0; i < N; ++i){ phi[i] = 0; s[i] = 0; f[i] = 0; } phi[1] = 1; for(int i = 2; i < N; ++i) if(phi[i] == 0) for(int j = i; j < N; j += i){ if(phi[j] == 0) phi[j] = j; phi[j] = phi[j] / i * (i - 1); } for(int i = 1; i < N; ++i) for(int j = i + i; j < N; j += i) f[j] += i * phi[j / i]; for(int i = 2; i < N; ++i) s[i] = s[i - 1] + f[i]; }}

上一篇：重定向和请求转发的区别

下一篇：uva 442矩阵链乘