Advertisement
alien_fx_fiend

F

Sep 5th, 2015
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.27 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cmath>
  4. #include <cstdio>
  5. #include <cstring>
  6. #include <deque>
  7. #include <iomanip>
  8. #include <iostream>
  9. #include <queue>
  10. #include <map>
  11. #include <numeric>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <utility>
  16. #include <vector>
  17.  
  18. #define INF 1000000000
  19. #define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
  20. #define FORC(cont, it) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
  21. #define pb push_back
  22.  
  23. using namespace std;
  24.  
  25. typedef unsigned long long ll;
  26. typedef pair<int, int> ii;
  27. typedef vector<int> vi;
  28. typedef vector<ii> vii;
  29. typedef vector<vi> vvi;
  30.  
  31. #define maxNum 1000000
  32.  
  33. ll mulmod(ll a, ll b, ll c) { // returns (a * b) % c, and minimize overflow
  34.     ll x = 0, y = a % c;
  35.     while (b > 0) {
  36.         if (b % 2 == 1) x = (x + y) % c;
  37.         y = (y * 2) % c;
  38.         b >>= 1;
  39.     }
  40.     return x % c;
  41. }
  42.  
  43. ll fastPow(ll x, ll n, ll MOD) {
  44.     ll ret = 1;
  45.     while (n) {
  46.         if (n & 1) ret = mulmod(ret, x, MOD);
  47.         x = mulmod(x, x, MOD);
  48.         n >>= 1;
  49.     }
  50.     return ret;
  51. }
  52.  
  53. // Miller-Rabin primality test
  54. bool isPrime(ll n) {
  55.     ll d = n - 1;
  56.     int s = 0;
  57.     while (d % 2 == 0) {
  58.         s++;
  59.         d >>= 1;
  60.     }
  61.     // It's garanteed that these values will work for any number smaller than 3*10**18 (3 and 18 zeros)
  62.     int a[9] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
  63.     FOR(i, 0, 9) {
  64.         bool comp = fastPow(a[i], d, n) != 1;
  65.         if(comp) FOR(j, 0, s) {
  66.             ll fp = fastPow(a[i], (1LL << (ll)j)*d, n);
  67.             if (fp == n - 1) {
  68.                 comp = false;
  69.                 break;
  70.             }
  71.         }
  72.         if(comp) return false;
  73.     }
  74.     return true;
  75. }
  76.  
  77. int main() {
  78.     ll N;
  79.     // Basically we get all the prime factors and use standard combinatorics to get number of divisors
  80.     // For every prime factor get the amount of times it appears and add 1, then multiply all those numbers
  81.     // For example 12=> 2pow2, 3pow1 => (2+1)*(1+1)=6
  82.     while (scanf("%lld", &N)!=EOF) {
  83.         // Optimization begins here
  84.         // This could be avoided and we would have much cleaner code
  85.         // Good to know this makes getting the factors 66% faster
  86.         // Instead of checking divisibility in every number from 2 to maxN
  87.         // We just check those that we know arent divisible by 2 and 3
  88.         // Get 2s
  89.         int ans = 1, cont=0;
  90.         while (!(N&1)) {
  91.             N >>=1;
  92.             cont++;
  93.         }
  94.         ans = cont + 1;
  95.         cont = 0;
  96.         // Get 3s
  97.         while (N%3==0) {
  98.             N /=3;
  99.             cont++;
  100.         }
  101.         ans *= cont + 1;
  102.         // Skip all numbers divisible by 2 and 3
  103.         for(int i=5; i<maxNum; i+=4) {
  104.             if (N < i) break;
  105.             cont = 0;
  106.             while (!(N%i)) {
  107.                 N /= i;
  108.                 cont++;
  109.             }
  110.             if(cont) ans *= cont + 1;
  111.             i += 2;
  112.             cont = 0;
  113.             while (!(N%i)) {
  114.                 N /= i;
  115.                 cont++;
  116.             }
  117.             if (cont) ans *= cont + 1;
  118.         }
  119.         // Optimization ends here
  120.         // If N is not 1 it means it is bigger than 1 million, N can be a product of 2 primes or a prime
  121.         // If N is a product of primes it can be a perfect square or a multiplications of different primes
  122.         if (N != 1) {
  123.             // First we check if it's a perfect square
  124.             // Take 50 away and iterate just to make sure we don't lose presition
  125.             ll sq = sqrt(N)-50;
  126.             while (sq*sq < N) sq++;
  127.             if (sq*sq == N) ans *= 3;
  128.             else {
  129.                 if (isPrime(N)) ans <<= 1;
  130.                 else ans <<= 2; // If it is not a prime it is a composite of 2 different primes
  131.             }
  132.         }
  133.         printf("%d\n", ans);
  134.     }
  135.     return 0;
  136. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement