DIFFICULTY:
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;
}