GOODARR - Editorial

editorial
, , , ,
1

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;
}
3 Likes