Question Link: https://www.spoj.com/problems/DIVFACT2/
Logic: There can be at most 1 prime factor from sqrt(n) to n.
#include<bits/stdc++.h>
#define int long long int
#define pb push_back
#define endl '\n’
int sieve[10001];
using namespace std;
vector vec;
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
for (int i=0;i<=1e4;i++) sieve[i]=1;
for (int i=2;ii<=1e4;i++){
if (sieve[i]){
for (int j=ii;j<=1e4;j+=i) sieve[j]=0;
}
}
for (int i=2;i<=1e4;i++){
if (sieve[i]) vec.pb(i);
}
int t; cin>>t;
while(t–){
int n,m; cin>>n>>m;
int ans=1;
for (int i=0;i<vec.size();i++){
if (n/vec[i]==0) break;
int base=vec[i],power=0;
while(n/base>=1){
power=(power+n/base)%m;
base*=vec[i];
}
ans=(ans*(power+1))%m;
}
if (n%2==0){
while(n%2==0){
n/=2;
}
}
for (int i=3;ii<=n;i+=2){
if (n%i==0){
while(n%i==0) n/=i;
}
}
if (n>vec[vec.size()-1]) ans=(ans2)%m;
cout<<ans<<endl;
}
}