11347 - Multifactorials

[H_Hima]

Hi

may anyone put some tricky cases for this problem.

thanks.

this is my code that got WA:

Code: Select all

#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;

long long MAX=1000000000;
long long devs[1002][25];
bool nums[1002];
int primes[1000];
int cnt;

map<int,int> facts[1001];
int counts[1002];

int main() {
    MAX*=MAX;
	int i,j,k,tt,n,t;
	cnt=0;
	nums[0]=nums[1]=false;
	for(i=2;i<1002;i++)
		nums[i]=true;
	for(i=2;i<500;i++) {
		if(nums[i]) {
			for(j=i+i;j<1001;j+=i) {
				for(tt=j,k=0;tt%i==0;tt/=i,k++);
				facts[j].insert(pair<int,int>(i,k));
				nums[j]=false;
			}
			facts[i].insert(pair<int,int>(i,1));
			primes[cnt++]=i;
		}
	}
	for(i=0;i<1001;i++)
		for(j=0;j<25;j++)
			devs[i][j]=0;
	map<int,int>::iterator it;
	cin>>n;
	char temp[100];
	string sss;
	for(t=0;t<n;t++) {
		cin>>i;
		cin.getline(temp,100);
		sss=temp;
		j=sss.length();
		if(devs[i][j]==0) {
			if(j>0) {
				for(k=0;primes[k]<=i&&k<cnt;k++)
					counts[primes[k]]=0;
				for(k=i;k>0;k-=j)
					for(it=facts[k].begin();it!=facts[k].end();it++)
						counts[it->first]+=it->second;
				devs[i][j]=1;
				for(k=0;k<cnt&&i>=primes[k];k++) {
					if(counts[primes[k]])
						devs[i][j]*=(counts[primes[k]]+1);
					if(devs[i][j]>MAX) {
						devs[i][j]=-1;
						break;
					}
				}
			}
			else {
				for(k=0;primes[k]<=i&&k<cnt;k++)
					counts[primes[k]]=0;
				for(it=facts[i].begin();it!=facts[i].end();it++)
					counts[it->first]+=it->second;
				devs[i][0]=1;
				for(k=0;k<cnt&&i>=primes[k];k++) {
					if(counts[primes[k]])
						devs[i][0]*=(counts[primes[k]]+1);
					if(devs[i][0]>MAX||devs[i][0]<0) {
						devs[i][0]=-1;
						break;
					}
				}
			}
		}
		cout<<"Case "<<t+1<<": ";
		if(devs[i][j]==-1)
			cout<<"Infinity"<<endl;
		else
			cout<<devs[i][j]<<endl;
	}

}

[Mushfiqur Rahman]

Try with this Input

Code: Select all

3
997!!!!!!!!!!!!!!!!!!!!
997!!!!!!!!!!!!!!!!!!!
997!!!!!!!!!!!!!!!!!!

Your program gives:

Code: Select all

Case 1: 140896402145280
Case 2: 15533828336517120
Case 3: 12524124635136000

But the actual Output will be:

Code: Select all

Case 1: 288555831593533440
Case 2: 994165013537095680
Case 3: Infinity

[shiplu_1320]

Why CE ? help someone.

Code: Select all

Removed

[greve]

The problem is your global variable named index. In the judge compiler's version of string.h there is a declaration of a function of this name, so rename this global variable and your code will compile.

[shiplu_1320]

Now i got WA? any body give me some test case.

Code: Select all

Removed after AC.

[MSH]

Hi,
I can't find why it gives run time error. I checked it for many cases and it hasn't any problem for those cases.
May anyone help me?!
This is my code got Run Time Error

Code: Select all

#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

#define Max 1001
#define MaxP 200

long long pNo[Max][MaxP];
bool prime[Max];
vector < vector < pair < long long,long long > > > v;
long long f(long long n, long long k){
	long long i = 0;
	while(!(n % k)){
		n /= k;
		i++;
	}
	return i;
}
int main(){
	long long i,j,k,l,x,c,n,m,t;
	memset(pNo,0,sizeof(pNo));
	memset(prime,1,sizeof(prime));
	c = 0;
	for(i=2;i<Max; ){
		pNo[i][c] = 1;
		for(j = i+i; j < Max; j += i){
			prime[j] = 0;
			pNo[j][c] = f(j,i);
		}
		i++;
		while(!prime[i])
			i++;
		c++;
	}
	v.resize(Max);
	for(i=2;i<Max;i++){
		for(j=0;j<MaxP;j++)
			if(pNo[i][j]){
				pair<long long,long long> p;
				p.first = j;
				p.second = pNo[i][j];
				v[i].push_back(p);
			}
	}
	string s;
	long long cnt[MaxP];
	cin>>t;
	for(i = 1; i <= t; i++){
		cin>>n;
		k = 0;
		getline(cin,s);
		for(j = 0; j < s.size(); j++)
			if(s[j] == '!')
				k++;
		if(!k){
			cout<<"Case "<<i<<": "<<n<<endl;
			continue;
		}
		memset(cnt,0,sizeof(cnt));
		for(j = 0, m = n; m - j*k > 0;j++){
			x = m - j * k;
			for(l = 0; l < v[x].size(); l++)
				cnt[v[x][l].first] += v[x][l].second;
		}
		unsigned long long inf = 1e18;
		long long mul = 1;
		for(j = 0; j < MaxP ;j++){
			mul *= (cnt[j] + 1);
			if(mul > inf){
				cout<<"Case "<<i<<": Infinity"<<endl;
				break;
			}
		}
			if(mul < inf)
				cout<<"Case "<<i<<": "<<mul<<endl;
	}
}

[Xmansk]

I don't understand the output.

Why for input 5! there is output 16? What does exactly mean "number of dividers"?

5! = 5*(5-1)*(5-2)*(5-3)*(5-4)
it should be correct, shouldn't it?

[Jan]

5! = 120.

The dividers are..
1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120.

So, there are 16 dividers, thus the result is 16.