fork(6) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #define MAXN 1000001
  4.  
  5. using namespace std;
  6.  
  7.  
  8. int main()
  9. {
  10.     int n;
  11.     cin >> n;
  12.     char is_prime[MAXN];
  13.     int d[MAXN],p[MAXN];
  14.     long long a[MAXN];
  15.     memset(is_prime,1,(n+1)*sizeof(char)); 
  16.     memset(a,0,(n+1)*sizeof(long long));
  17.     is_prime[0] = 0;
  18.     is_prime[1] = 0;
  19.     for (int i=2; i * i<=n; i++)
  20.             if (is_prime[i])
  21.             {
  22.                     if (i * 1ll * i <= n)
  23.                             for (int j=i*i; j<=n; j += i)
  24.                             {
  25.                                     is_prime[j] = 0;
  26.                                     p[j] = i;
  27.                                     d[j] = j/i;
  28.                             }
  29.             }
  30.         for (int i=2;i<=n;i++)
  31.         {
  32.             if (is_prime[i])
  33.             {
  34.                 d[i] = 1;
  35.                 p[i] = i;
  36.             }
  37.         }
  38.         for(int i=1;i<=n;i++)
  39.         {
  40.             int k = i;
  41.             while (k!=1)
  42.             {
  43.                 int div = p[k];
  44.                 ++a[div];
  45.                 k = d[k];
  46.             }
  47.         }
  48.         long long ans = 1;
  49.         for(int i=1;i<=n;i++)
  50.             if (is_prime[i])
  51.                 ans = (ans * (1 + 2 * a[i]))%1000007;
  52.         cout << ans;
  53.         return 0;
  54. }
Runtime error #stdin #stdout 0.02s 2720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EW1iE
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

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!