Problem Link
(COOLGUYS Problem - CodeChef)
My Solution
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define lli long long int
#define vi vector<lli>
#define vii vector<pair<lli,lli> >
#define pb push_back
#include<string>
#define mp map<string,lli>
#define mpp map<char,lli>
#define ss set<lli>
#define MOD 1000000007
//#define N 100001
#define test lli t;cin>>t;while(t--)
using namespace std;
lli countFactor(lli n)
{
lli cnt=0;
for(lli i=1;i<=sqrt(n);i++)
{
if(n%i==0)
{
cnt+=1;
if(n/i!=i)
cnt+=1;
}
}
return cnt;
}
int main()
{
fast
test
{
lli n;
cin>>n;
lli cnt=0;
for(lli i=1;i<=n;i++)
cnt+=countFactor(i);
cout<<cnt<<"/"<<n*n<<endl;
}
}
You have to reduce the fraction too. Make the following changes.
lli n;
cin >> n;
lli cnt = 0;
for(lli i = 1; i <= n; i++)
cnt += countFactor(i);
lli num = cnt;
lli den = n * n;
lli g = gcd(num, den);
num /= g; den /= g;
cout << num << "/" << den << endl;
after some changes it’s given tle.
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define lli long long int
#define vi vector<lli>
#define vii vector<pair<lli,lli> >
#define pb push_back
#include<string>
#define mp map<string,lli>
#define mpp map<char,lli>
#define ss set<lli>
#define MOD 1000000007
//#define N 100001
#define test lli t;cin>>t;while(t--)
using namespace std;
lli countFactor(lli n)
{
lli cnt=0;
for(lli i=1;i<=sqrt(n);i++)
{
if(n%i==0)
{
cnt+=1;
if(n/i!=i)
cnt+=1;
}
}
return cnt;
}
lli gcd(lli a, lli b)
{
if (b == 0)
return a;
return gcd(b, a % b);
}
int main()
{
fast
test
{
lli n;
cin>>n;
lli cnt=0;
for(lli i=1;i<=n;i++)
cnt+=countFactor(i);
lli num = cnt;
lli den = n * n;
lli g = gcd(num, den);
num /= g; den /= g;
cout << num << "/" << den << endl;
}
}
Um, actually I just figured out that this approach gives TLE. You have to optimise it to get AC.
