Problem 8: Factors of Factors

Points:

Small Case: 5 Answer: 704

Large Case: 15 Answer: 18694892480

Let D be set of prime factors of an integer N.
A function f(N,d) is defined as

f(N,d) = No. of integers 'x' such that gcd(N,x) is 'd'.

where d is an element of D.

Given the value of N, find

Small Case:N=2112
Large Case: N=65432123456

Solution:

The value of f(N,d) is equal to the Euler totient of (N/d).

Reference:Robert D. Carmichael, The Project Gutenberg EBook The Theory of Numbers,2004,Section 2.4.

Code:

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#define ll long long int
#define MAX 255800ll
using namespace std;
bool ar[MAX+1]={0};
ll pr[MAX]={0},len=0;
ll func(ll n)
{
		ll ans=n;
        ll y=(ll)sqrt(n+1);
        for(ll i=0,x=0;pr[i]<=y && i<len && pr[i]<=n;i++)
        {
            if(n%pr[i]==0)
            {
                x=pr[i];
                ans=(ans*(x-1))/x;
                while(n%x==0)
                    n/=x;
            }
        }
        if(n>1)
            ans=(ans*(n-1))/n;
		return ans;
}
int main()
{
    ll i,j,n,n1,ans=0,y;
    for(i=2;i<=MAX;i++)
        if(ar[i]==0)
        {
            pr[len++]=i;
            for(j=i<<1;j<=MAX;j+=i)
                ar[j]=1;
        }
    n=65432123456ll;
    n1=n;
    ans=0;
    y=(ll)sqrt(n+1);
    for(i=0;pr[i]<=y && i<len && pr[i]<=n;i++)
    {
        if(n%pr[i]==0)
        {
            ans+=func(n1/pr[i]);
            while(n%pr[i]==0)
                n/=pr[i];
        }
    }
    if(n>1)
        ans+=func(n1/n);
    printf("%lld\n",ans);
    return 0;
}