1 / 2
Jun 2020

I have used legendre’s formula for solving the problem.But I can’t seem to decipher the reason behind the wrong answer.

     #include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<b;i++)
#define NUM 1000000007
#define MAX 50001

using namespace std;

typedef long long int ll;

vector<int> primes;
bool isprime[MAX];

void seive()
{
	memset(isprime,true,sizeof(isprime));
	
	for(int i=2;i*i<MAX;i++)
	{
		if (isprime[i])
		{
			primes.push_back(i);
			for(int j=i*i;j<MAX;j+=i)
			{
				isprime[j]=false;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	seive();
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		 int ans=1;
		 for(auto i :primes)
	   	 {
			ll curr = i;
			int count = 0;
			while(curr <=  n)//legendre's  formula
			{
				count += n/curr;
				curr = curr*i;
			}
			ans = (ll) ans*(count+1)%NUM;
		 }
		 cout<<ans<<endl;
	    
	}
	return 0;
}
  • created

    Jun '20
  • last reply

    Jun '20
  • 1

    reply

  • 524

    views

  • 2

    users

18 days later

Try these:

2
2222
33333

Expected answers

556327185
247240385