PROBLEM LINK:
Author: Sai Teja
Tester: Sai Teja
Editorialist: Sai Teja
DIFFICULTY:
EASY
PREREQUISITES:
Sieve of Eratosthenes
PROBLEM:
Given a number N,we need to compute the sum of ,product of elements in a subset,of all subsets formed from the factors of N.
EXPLANATION:
We can compute the factors of a number in
O(sqrt(N)).Let the value to be computed be S(S=0 initially).Let us define S as the solution formed from the factors read so far.If we read a new factor for the number,
then the solution would be (S=S+f.S+f,f is the new factor).
Reason for the three terms:
Part 1(S) and Part2(f.S):
This new factor can be multiplied with all the subsets formed inititally forming (f.S) and the initial subsets must also remain forming (S).
Part 3(f):
So far we have covered all the subsets having the element f except one.The singleton set having f.So we add (f).
Example:
N=4
S=0,f=1
S=(0+0.1+1)=1
S=1,f=2
S=(1+1.2+2)=(1+2+1.2)
S=(1+2+1.2),f=4
S=((1+2+1.2)+(1+2+1.2).4+4)=(1+2+4+1.2+1.4+2.4+1.2.4)=29
We cannot find the factors for every test case with O(sqrt(N)) as it would cross the time limit.So we use the concept of Sieve to precompute the solutions.The time complexity of precomputations would be O(NlogN).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
int main()
{
ll ans[100001];
memset(ans,0,sizeof(ans));
for(ll i=1;i<=100000;i++)
{
for(ll j=1;i*j<=100000;j++)
ans[i*j]=(ans[i*j]*(1+i)+i)%mod;
}
ll t,n;
cin>>t;
while(t--)
{
cin>>n;
cout<<ans[n]<<endl;
}
return 0;
}