 MEDIUM

# PREREQUISITES:

Number Theory, Math

# PROBLEM:

Given a number N we have to represent it as the sum of \phi values of distinct numbers less than or equal to 1000000.

# QUICK EXPLANATION:

Using euler totient function divisor sum property:

sum of euler totient function of all the the positive divisors of a number is equal to the number.

# EXPLANATION:

euler totient function of a number(N) is the number of integers from 1 to N that gives gcd=1 with N.

An useful property can be used directly to the problem. A number N can represented as the summation of the phi values of all its divisors.

All the divisors can be found in O(\sqrt(N))

# ALTERNATE EXPLANATION:

euler totient function of a number(2^k) = 2^k - 2^k-1

The property to note here is that \phi(pk)=pk - pk-1

where p is a prime number. Since 2 is prime number we can use this property.

Thus we can simple find the binary representation of the number and each set bit multiplied by 2 is our answer.

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
vector<int>ans;
for(int i=1;i*i<=N;i++)
{
if(N%i==0)
{
ans.push_back(i);
if(N!=(i*i))
ans.push_back(N/i);
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";
cout<<endl;
}

Tester's Solution
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
vector<int>ans;
for(int i=20;i>=0;i--)
{
if(N&(1<<i))
{
ans.push_back((1<<(i+1)));
}
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<" ";
cout<<endl;
}

3 Likes