fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Ramen {
  5.  
  6.     static final long MOD = 1_000_000_007;
  7.  
  8.     public static void main(String[] args) throws IOException {
  9.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  10.         PrintWriter out = new PrintWriter(System.out);
  11.         long N = Long.parseLong(br.readLine());
  12.         out.println(solve(N) % MOD);
  13.         br.close();
  14.         out.close();
  15.     }
  16.  
  17.     static long solve(long N) {
  18.         long ans = 1;
  19.         for (long d = 1; d * d <= N; d++) {
  20.             if (N % d == 0) {
  21.                 long inc = d * phi(d);
  22.                 ans = (ans + inc % MOD) % MOD;
  23.                 if (d * d != N) {
  24.                     inc = (N/d % MOD) * phi(N/d);
  25.                     ans = (ans + inc % MOD) % MOD;
  26.                 }
  27.             }
  28.         }
  29.         return (ans * (N%MOD) % MOD) * 500000004 % MOD;
  30.         // 500000004 is 2^-1 mod (10^9 + 7)
  31.     }
  32.  
  33.     static long phi(long N) {
  34.         long ans = N;
  35.         for (long p = 2; p * p <= N; p++) {
  36.             if (N % p == 0) {
  37.                 while (N % p == 0) N /= p;
  38.                 ans -= ans / p;
  39.             }
  40.         }
  41.         if (N > 1) ans -= ans / N;
  42.         return ans % MOD;
  43.     }
  44.  
  45. }
  46.  
Success #stdin #stdout 0.1s 54800KB
comments (?)
stdin
copy 
6
stdout
copy 
66
https://ideone.com/NoUiyQ
language:
Java (HotSpot 12)
created:
301 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!