In the setter’s solution what is the use of this code fragment
if(a[i]!=1)
{
if(m.find(a[i])!=m.end())
m[a[i]]++;
else
m.insert(MP(a[i],1));
from line 85 to 90
I put that in comments and ran the program and it gave the correct o/p for test cases. I don’t understand it’s use. After dividing with all the prime numbers shouldn’t a[i] necessarily be 1.
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
if(t>=1 && t<=100)
{
while(t–)
{
int n;
scanf("%d",&n);
if(n>=1&&n<=10)
{
long int a, total=1;
while(n–)
{
scanf("%ld",&a);
if(a>=2&&a<=1000000)
total*=a;
}
int count=0;
for(int i=1;i<=total;i++)
{
if(total%i==0)
count++;
}
printf("%d\n",count);
}
}
}
return 0;
}
Can anyone provide critical input. My solutions keeps getting WA, however, when comparing to AC code gives same output.
from sys import stdin
from collections import Counter
from math import sqrt,ceil
def primes(n):
""" Input n>=6, Returns a list of primes, 2 <= p < n """
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
def factor(n):
upper = n
i = 0
while sieve[i] <= ceil(sqrt(upper)):
while n%sieve[i]==0:
n/=sieve[i]
if sieve[i] not in factors:
factors[sieve[i]]=0
factors[sieve[i]]+=1
i+=1
if(n>1):
if upper not in factors:
factors[upper]=0
factors[upper]+=1
sieve = primes(10000)
factors = {}
def solve():
N = int(stdin.readline())
numbers = map(int,stdin.readline().split())
#print([i for i in numbers])
factors.clear()
for num in numbers:
factor(num)
tot = 1
for num in factors:
#print("fac",num,factors[num])
tot *= (factors[num]+1)
print tot
def main():
tc = int(stdin.readline())
for i in range(1,tc+1):
solve()
if __name__=="__main__":
main()whats the problem wid following ? i got a WA
#include<stdio.h>
#include<math.h>
int primes[1000000];
int a[1000000];
void gen_primes(int n)
{
int i,j;
for(i=0;i<n;i++)
primes[i]=1;
for(i=2;i<=(int)sqrt(n);i++)
{
if(primes[i])
{
for(j=i;j*i<n;j++)
{
primes[i*j]=0;
}
}
}
}
main()
{
int t,n,i;
long long int p,x;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<(int)sqrt(n);i++)
{
a[i]=0;
}
gen_primes(n);
while(n--)
{
scanf("%lld",&x);
for(i=2;i<=(int)sqrt(n);i++)
{
if(primes[i])
{
if(x%i==0)
{
a[i]=a[i]+(long long int)((double)log(x)/(double)log(i));
}
}
}
}
p=1;
for(i=2;i<=(int)sqrt(n);i++)
{
if(a[i])
{
p=p*(a[i]+1);
}
}
printf("%lld\n",p);
}
return 0;
}my code is running fine on the first time… but in second test case giving erronous output… please help…
#include<stdio.h>
int freq[1000000];
int sum;
void count(long long int x)
{
int i;
for(i=2;;i++)
{
while(x%i==0)
{
freq[i]++;
x=x/i;
sum++;
}
if(x==1)
break;
}
}
int main(void)
{
int t,n,p,y,i;
long long int x;
scanf("%d",&t);
while(t--)
{
p=1;
y=0;
sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
freq[i]=0;
while(n--)
{
scanf("%lld",&x);
count(x);
}
for(i=0;;i++)
{
if(freq[i]!=0)
{
p=p*(freq[i]+1);
y=y+freq[i];
if(y==sum)
break;
}
}
printf("%d\n",p);
}
return 0;
}Where Am i Going Wrong , Its Always SIGSEV and TLE on my Submission :’( , Plz help me Fast i Need to Brace up For IOI
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void solve(long long int *primes,long long int *n )
{
long long int *z = (long long int *)calloc(1001,sizeof
(long long int));
while(*n>1)
{
for(long long int i=0;i<168;i++)
{
if(*n%primes[i]==0){z[i]++;*n= *n/primes[i];i--;}
}
}
long long int prod=1;
for(long long int k=0;k<168;k++)if(z[k]!=0)prod*=(z[k]+1);
printf("%lld \n",prod);
//for(long int i=0;i<n&&primes[i]!=0;i++)printf("%ld \n",primes[i]);
}
int main()
{
long long int *primes;
primes = (long long int *)calloc(1001,sizeof(long long int));
primes[0]=2;
primes[1]=3;
long long int index=2;
for(long long int z=5;z<=1001;z+=2)
{
long long int fact=0;
for(long long int i=0;i<1001&&primes[i]!=0;i++)
{
if(z%primes[i]==0){fact++;break;};
}
if (fact==0)
{
primes[index]=z;
index++;
}
}
long long int t;
scanf("%lld",&t);
while(t--){
long long int n,prod=1,temp;
scanf("%lld",&n);
for(long long int i=0;i<n;i++){scanf("%lld",&temp);prod*=temp;}
solve(primes,&prod);
}
}Hey whats wrong in my code here?
program FACTORS;
uses Math;
var
t,n,num,product:longint;
function factors(fact:longint):longint;
var
no:longint = 0;
x:longint;
begin
for x := 1 to floor(sqrt(fact)) do
begin
if fact mod x = 0 then
begin
if x*x = fact then inc(no,1)
else inc(no,2);
end;
end;
factors := no;
end;
begin
readln(t);
while t <> 0 do
begin
readln(n);
product := 1;
while n <> 0 do
begin
read(num);
product := product * num;
dec(n);
end;
writeln(factors(product));
dec(t);
end;
end.
I am getting runtime error NZEC.
I have been trying to debug my code for so long still not able to figure out why it is giving a WA for the basic cases. Please if anyone could tell me where am I going wrong?
This is the link to my solution.
https://www.codechef.com/submit/complete/8669014
nice explanation.
I used sieve of eratosthenes to get all prime factors of number
https://www.codechef.com/viewsolution/14084014
WHY IS THIS SOLUTION GETTING A WA ON LAST CASE PLZ HELP!!
it works… I have used “other” array for those primes
Can u provide any testcase where it fails…
In your code, you are checking whether a[i] == 1 towards the end. But can you give me a case where it wont be equal to 1. Wont the prime numbers stored in the list make sure that the smallest number is being factorized first and then proceed to the largest??
A simple modification of Sieve of Erastothenes will also prove to be helpful. The following is what I used.
f[i] == 0 if i is prime, and if i is prime, then f[i] will have the smallest prime that will divide it.
for (int i = 2; i <= N; i++)
if (!f[i]) for (int j = i+i; j <= N; j += i) if (!f[j]) f[j] = i;
f[i] will help a lot to find all the prime divisors of a number.
http://www.codechef.com/viewsolution/2894661
A shorter solution with the same concept + the subtle modification of the sieve to store prime factor info.
I Even Tried Putting The Sieve Out , But Still i was only able to Solve only One Subtask !!! :’(
Any special reason for using char type of array for storing primes by setter ?
I came up with the following code, but it fails for some test cases. Can anyone help?
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int testCases=sc.nextInt();
int count=0;
while(testCases-->0) {
int numValues=sc.nextInt();
int prod=1;
for(int i=0;i<numValues;i++) {
int temp=sc.nextInt();
prod=prod*temp;
}
for(int i=1;i<=Math.sqrt(prod);i++) {
if(prod%i==0) {
if(prod/i == i) {
count++;
}else {
count+=2;
}
}
}
System.out.println(count);
count=0;
}
sc.close();
}why is it that a particular test case messes up the output of the testcases that follows it? for example, with the following code ( CodeChef: Practical coding for everyone) the same sample test cases given in the question gives different output when the order of these test cases are changed. Also, the same code when run in different IDE like that in GeeksforGeeks is giving completely different answers ( for a different test set though), why is it like that? can somebody please help me out?