Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <bitset>
- #include <cmath>
- #include <cstdio>
- #include <cstring>
- #include <deque>
- #include <iomanip>
- #include <iostream>
- #include <queue>
- #include <map>
- #include <numeric>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <utility>
- #include <vector>
- #define INF 1000000000
- #define FOR(i, a, b) for(int i=int(a); i<int(b); i++)
- #define FORC(cont, it) for(typeof((cont).begin()) it = (cont).begin(); it != (cont).end(); it++)
- #define pb push_back
- using namespace std;
- typedef unsigned long long ll;
- typedef pair<int, int> ii;
- typedef vector<int> vi;
- typedef vector<ii> vii;
- typedef vector<vi> vvi;
- #define maxNum 1000000
- ll mulmod(ll a, ll b, ll c) { // returns (a * b) % c, and minimize overflow
- ll x = 0, y = a % c;
- while (b > 0) {
- if (b % 2 == 1) x = (x + y) % c;
- y = (y * 2) % c;
- b >>= 1;
- }
- return x % c;
- }
- ll fastPow(ll x, ll n, ll MOD) {
- ll ret = 1;
- while (n) {
- if (n & 1) ret = mulmod(ret, x, MOD);
- x = mulmod(x, x, MOD);
- n >>= 1;
- }
- return ret;
- }
- // Miller-Rabin primality test
- bool isPrime(ll n) {
- ll d = n - 1;
- int s = 0;
- while (d % 2 == 0) {
- s++;
- d >>= 1;
- }
- // It's garanteed that these values will work for any number smaller than 3*10**18 (3 and 18 zeros)
- int a[9] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
- FOR(i, 0, 9) {
- bool comp = fastPow(a[i], d, n) != 1;
- if(comp) FOR(j, 0, s) {
- ll fp = fastPow(a[i], (1LL << (ll)j)*d, n);
- if (fp == n - 1) {
- comp = false;
- break;
- }
- }
- if(comp) return false;
- }
- return true;
- }
- int main() {
- ll N;
- // Basically we get all the prime factors and use standard combinatorics to get number of divisors
- // For every prime factor get the amount of times it appears and add 1, then multiply all those numbers
- // For example 12=> 2pow2, 3pow1 => (2+1)*(1+1)=6
- while (scanf("%lld", &N)!=EOF) {
- // Optimization begins here
- // This could be avoided and we would have much cleaner code
- // Good to know this makes getting the factors 66% faster
- // Instead of checking divisibility in every number from 2 to maxN
- // We just check those that we know arent divisible by 2 and 3
- // Get 2s
- int ans = 1, cont=0;
- while (!(N&1)) {
- N >>=1;
- cont++;
- }
- ans = cont + 1;
- cont = 0;
- // Get 3s
- while (N%3==0) {
- N /=3;
- cont++;
- }
- ans *= cont + 1;
- // Skip all numbers divisible by 2 and 3
- for(int i=5; i<maxNum; i+=4) {
- if (N < i) break;
- cont = 0;
- while (!(N%i)) {
- N /= i;
- cont++;
- }
- if(cont) ans *= cont + 1;
- i += 2;
- cont = 0;
- while (!(N%i)) {
- N /= i;
- cont++;
- }
- if (cont) ans *= cont + 1;
- }
- // Optimization ends here
- // If N is not 1 it means it is bigger than 1 million, N can be a product of 2 primes or a prime
- // If N is a product of primes it can be a perfect square or a multiplications of different primes
- if (N != 1) {
- // First we check if it's a perfect square
- // Take 50 away and iterate just to make sure we don't lose presition
- ll sq = sqrt(N)-50;
- while (sq*sq < N) sq++;
- if (sq*sq == N) ans *= 3;
- else {
- if (isPrime(N)) ans <<= 1;
- else ans <<= 2; // If it is not a prime it is a composite of 2 different primes
- }
- }
- printf("%d\n", ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement