Pollard's Rho Algorithm - Answer Code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
using namespace std;
typedef long long int lli;

lli mul(lli a, lli b, lli n) {
    return (__int128)a*b % n;
}

lli power(lli a, lli d, lli n) {
    lli res = 1;
    a %= n;
    while (d > 0) {
        if (d % 2 == 1) {
            res = mul(res, a, n);
        }
        a = mul(a, a, n);
        d /= 2;
    }
    return res;
}

int checklist[] = {2,3,5,7,11,13,17,19,23,29,31,37};
bool millerRabin(lli n) {
    if(n==2) {
        return true;
    }
    if(n%2==0) {
        return false;
    }
    bool ret = true;
    for(lli a : checklist) {
        if(a%n==0) {
            return true;
        }
        lli d = n-1;
        while(true) {
            lli pow = power(a, d, n);
            if(pow==n-1) {
                break;
            }
            if(d%2!=0) {
                if(pow==1 || pow==n-1) {
                    break;
                } else {
                    return false;
                }
            }
            d = d/2;
        }
    }
    return ret;
}

void pollardRho(lli n, set<lli> &v) {
    if(n==1) {
        return;
    }
    if(n%2==0) {
        v.insert(2);
        pollardRho(n/2, v);
        return;
    }
    if(millerRabin(n)) {
        v.insert(n);
        return;
    }
    lli x = (rand()%(n-2))+2;
    lli y = x;
    lli c = (rand()%(n-1))+1;
    lli d = 1;
    while(d==1) {
        x = (power(x, 2, n) + c)%n;
        y = (power(y, 2, n) + c)%n;
        y = (power(y, 2, n) + c)%n;
        d = gcd(abs(x-y), n);
        if(d==n) {
            pollardRho(n, v);
            return;
        }
    }
    pollardRho(n/d, v);
    pollardRho(d, v);
    return;
}

int main(void) {
    srand(time(NULL));
    lli n = 0;
    scanf("%lld", &n);
    set<lli> divisors;
    pollardRho(n, divisors);
    set<lli>::iterator pos;
    for(pos = divisors.begin();pos!=divisors.end();++pos) {
        n = (n / (*pos)) * (*pos - 1);
    }
    printf("%lld", n);
}