fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int N = 1e6 + 5;
  5. long long indian_multiplication(long long a, long long b, long long mod)
  6. {
  7.     if (b == 0)
  8.         return 0LL;
  9.  
  10.     long long half = indian_multiplication(a, b / 2LL, mod) % mod;
  11.  
  12.     if (b & 1)
  13.         return (half + half + a) % mod;
  14.     else
  15.         return (half + half) % mod;
  16. }
  17. long long modular_exponentiation(long long a, long long b, long long mod)
  18. {
  19.     if (b == 0)
  20.         return 1LL;
  21.  
  22.     long long half = modular_exponentiation(a, b / 2LL, mod) % mod;
  23.     long long product = indian_multiplication(half, half, mod);
  24.  
  25.     if (b & 1)
  26.         return indian_multiplication(product, a, mod);
  27.     else
  28.         return product;
  29. }
  30. bool fermat_checking(long long n, int k = 50)
  31. {
  32.     if (n < 4)
  33.         return n == 2 || n == 3;
  34.  
  35.     if (n != 2 && n % 2 == 0)
  36.         return false;
  37.  
  38.     for (int i = 1; i <= k; ++i)
  39.     {
  40.         long long a = 2 + rand() % (n - 3);
  41.         if (modular_exponentiation(a, n - 1, n) != 1)
  42.             return false;
  43.     }
  44.  
  45.     return true;
  46. }
  47. vector < int > eratosthenes_sieve(int max_value)
  48. {
  49.     vector < bool > is_prime(max_value + 1, true);
  50.     is_prime[0] = is_prime[1] = false;
  51.  
  52.     for (int i = 2; i * i <= max_value; ++i)
  53.         if (is_prime[i])
  54.             for (int j = i * i; j <= max_value; j += i)
  55.                 is_prime[j] = false;
  56.  
  57.     vector < int > primes;
  58.     for (int i = 2; i <= max_value; ++i)
  59.         if (is_prime[i])
  60.             primes.push_back(i);
  61.  
  62.     return primes;
  63. }
  64.  
  65. int solution(int n)
  66. {
  67.     vector < int > primes = eratosthenes_sieve(1000000);
  68. 	long long res = 1;
  69.     for (int p : primes)
  70.     {
  71.         if (p * p * p > n)
  72.             break;
  73.  
  74.         int cnt = 0;
  75.         while (n % p == 0)
  76.         {
  77.             n /= p;
  78.             ++cnt;
  79.         }
  80.  
  81.         res *= (cnt + 1);
  82.     }
  83.     if (fermat_checking(n))
  84.         res *= 2LL;
  85.     else
  86.     {
  87.         int squaroot = sqrt(n);
  88.         if (squaroot * squaroot == n && fermat_checking(squaroot))
  89.             res *= 3;
  90.         else if (n != 1)
  91.             res *= 4;
  92.     }
  93.     return res;
  94. }
  95. main() {
  96.     ios_base::sync_with_stdio(false);
  97.     cin.tie(NULL); cout.tie(NULL);
  98.     int n;
  99.     cin >> n;
  100.     if (n <= 1e8) {
  101.         int k = sqrt(n);
  102.         if (k * k == n) {
  103.             cout << "WA";
  104.             return 0;
  105.         }
  106.         for (int i = 2; i <= k; ++i) {
  107.             if (n % i == 0) {
  108.                 cout << "WA";
  109.                 return 0;
  110.             }
  111.         }
  112.         cout << "AC";
  113.         return 0;
  114.     }
  115.     if (solution(n) > 2) {
  116.         cout << "WA";
  117.     }
  118.     else {
  119.         cout << "AC";
  120.     }
  121.  
  122. }
  123.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
WA
https://ideone.com/92hxKR
language:
C++14 (gcc 8.3)
created:
2 days 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!