Page 2 of 3
Posted: Thu Oct 21, 2004 10:27 pm
My first mistake was not including 1000000 in my pre calculations.

Fixed that and got AC

Posted: Thu Oct 21, 2004 10:41 pm
My first mistake was not including 1000000 in my pre calculations.

Fixed that and got AC

### 10680 can u help

Posted: Sun Oct 31, 2004 12:04 am
anyone wht got ac in this problem can u give me the output for these inputs

128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
25
125
625
3125
15625
78125
390625

### output..

Posted: Sun Oct 31, 2004 9:54 am
My AC program produces the following output..
2
6
2
2
2
4
4
6
6
6
4
2
6
4
8
8
4
8
6
4

Posted: Tue Nov 09, 2004 3:40 am
I have passed all the test cases above. But still WA.Who can tell me why?
Is there any possible that if n=1 the output should be 1.

Posted: Wed Mar 30, 2005 10:39 am
1. generate all primes upto 10^6

2. generate all powers of each prime

Code: Select all

``````   for ( i = 0; i <= MAX; ++i ) D[i] = 1;

for ( i = 1L; (1L<<i) <= MAX; ++i )
{
D[(1L<<i)] = 2L;
}
for ( i = 3L; i < MAXSQRT; i += 2L )
{
if ( isprime(i) )
{
for ( j = i; j <= MAX; j *= i )
{
D[j] = i;
}
}
}
for ( ; i <= MAX; i += 2L )
{
if ( isprime(i) )
{
D[i] = i;
}
}
``````
3. calculate the lcm using the following

Code: Select all

``````         lcm (n) = lcm(n-1) * D(n),
where
D(n) = n ,iff n is prime
D(n) = p, where n = p^k, k is any +ve integer and p is a prime
D(n) = 1, otherwise
``````

Code: Select all

``````    D[1] = 1L;
for ( i = 2L; i <= MAX; ++i )
{
if ( D[i] == 5L )
{
D[i] = (D[i-1]>>1L);
}
else
{
D[i] = (D[i]%1000000L)*(D[i-1]%1000000L);
}
while ( (D[i]%10L) == 0 )
D[i] /= 10L;
D[i] %= 1000000L;
}
``````
Any thoughts regarding the algorithm I am using?

Regards,
Suman.

### 10680 - TLE! Why?

Posted: Tue Oct 04, 2005 9:33 am
I don't know why TLE
How can I speed up a program?

#include <stdio.h>
#include <math.h>
#include <memory.h>

const int MAX=1000001;
const int SqrtMAX = (int)sqrt(MAX);
int m[MAX];
int i,n;

void gen_mas_m(void)
{
int i,j;
memset(m,127,sizeof(m)); m[0] = m[1] = 1;
for(i=2;i<=SqrtMAX;i++)
if (m[i] == 0x7F7F7F7F)
{
for(j=i*i;j<=MAX;j+=i) m[j] = 0;
for(j=i;j<=MAX;j*=i) m[j] = i % 10;
}
for(i=SqrtMAX;i<=MAX;i++)
if (m[i] == 0x7F7F7F7F) m[i] = i % 10;
}

void main(void)
{
gen_mas_m();
for(i=2;i<=MAX;i++)
{
if (!m[i]) m[i] = 1;
m[i] = m[i]*m[i-1] % 100;
if (m[i] % 10 == 0) m[i] = m[i] / 10;
}
while (scanf("%d",&n), n>0)
printf("%d\n",m[n] % 10);
}

### Re: 10680 - TLE! Why?

Posted: Sat Dec 10, 2005 11:56 pm
medv wrote:int m[MAX];
int i,n;
...
..for(i=2;i<=MAX;i++)
..{
....if (!m[i]) m[i] = 1;..
....m[i] = m[i]*m[i-1] % 100;
....if (m[i] % 10 == 0) m[i] = m[i] / 10;
..}
at the end of the loop if i==MAX you change the value of m[MAX]. But m[MAX] is out of the array bounds (0..MAX-1), thus you may corrupt the information stored in other variable.

### 10680

Posted: Fri Feb 03, 2006 2:02 pm
Plz help me...
How can i calculate LCM?
p.s. Please don`t delete this question. It is 10680!

Posted: Fri Feb 03, 2006 3:07 pm
scidong wrote:How can i calculate LCM?
LCM of two numbers is: lcm(a,b) = a*b/gcd(a,b).
LCM of n numbers can be computed as: lcm(a1,a2,...,a_n) = lcm(a1, lcm(a2, a3, ..., a_n)).
There is also another way to compute LCM: exponent of a prime p in factorization of lcm(a1, a2, ..., a_n) is the maximum exponent of that prime in factorizations of a1, a2, ..., a_n.

### 10680 WA

Posted: Sun Jul 02, 2006 5:08 am
Can anyone say where is wrong?
I try to solve it but fault

Code: Select all

``````#define MAX 78599
int a[1000009];
int prime[MAX]={2,3,5},pows[168];
void calprime()
{
int i,j,k,flag;
for(i=3,j=7;i<MAX;j++,flag=1)
{
for(k=0;prime[k]*prime[k]<=j;k++)
if(j%prime[k]==0)
{
flag=0;
break;
}
if(flag)
prime[i++]=j;
}
}
void precal()
{
int i,j,k=168,min,who,temp,last,five=0,two=0;
a[1]=1;
for(i=0;i<168;i++)
pows[i]=prime[i];
for(min=12345678,j=2;;min=12345678)
{
for(i=0;i<168;i++)
if(min>pows[i])
{
min=pows[i];
who=i;
}
if(prime[k]<min)
{
who=k;
min=prime[k];
k++;
}
for(;j<=min&&j<=1000000;j++)
a[j]=a[j-1];
if(j>1000000)
break;
if(who==2)
{
five++;
last=(1<<(two-five))%10;
for(i=1;i<168;i++)
{
if(i==2)
continue;
last*=(pows[i]/prime[i])%10;
last%=10;
}
for(i=168;i<k;i++)
{
last*=prime[i]%10;
last%=10;
}
a[min]=last;
pows[who]*=prime[who];
}
else
{
if(who==0)
two++;
a[min]*=prime[who]%10;
a[min]%=10;
if(who<168)
pows[who]*=prime[who];
}
}
}
int main()
{
int n,i;
calprime();
precal();
while(scanf("%d",&n),n)
printf("%d\n",a[n]);
}
``````

### Re: 10680 WA

Posted: Sun Jul 23, 2006 11:17 pm
a123123123888 wrote:Can anyone say where is wrong?
I try to solve it but fault
It's really interesting that your solution gets WA, while my gets AC, as both of them give the same answers to all numbers between 1 and 1000000.

### Re: 10680 WA

Posted: Sun Jul 23, 2006 11:20 pm
and btw, if there is a thread on a particular problem, please, use that thread and do not create a new one.

### 10680

Posted: Fri Aug 04, 2006 8:38 pm
my code gives wrong output for some input like 78125. but why? plz help me.

Code: Select all

``````#include<stdio.h>
#include<math.h>
#include<string>
#include<iostream>
#include<stdlib.h>
#include<ctype.h>
using namespace std;

#define tt long long
#define type int
#define size_ 1000001
#define DIGIT 1000000

bool prime[size_];
bool flag[size_];
int arr[size_];
int P[size_];

void seive(){

memset(prime,true,sizeof(prime));
prime[0]=false;
prime[1]=false;
for(int i=2;i*i<=size_;i++){

if(prime[i]){

for(int j=i*i;j<=size_;j+=i){

prime[j]=false;

}

}

}

}

void to_power(){

memset(flag,false,sizeof(flag));
for(int i=0;i<size_;i++){

if(prime[i]){

for(int j=i*i;j<size_ && j>0;j=j*i){

flag[j]=true;
P[j]=i;
}
}
}

}

tt extra_zero(tt a){

while(a%10==0){

a/=10;
}

return a;
}

tt truncate_digits(tt a){

return a%DIGIT ;

}

int last_digit(tt a){

return a%10;

}
void lcm(){

arr[0]=0;
arr[1]=1;
tt prev;
prev = 1;
for(int i=2;i<=size_;i++){

//		printf("i= %d  prev_before=  %I64d  ",i,prev);

//		printf("is_prime[%d]=%d  is_pow[%d]=%d  ",i,prime[i],i,P[i]);
if(prime[i]){

prev*=i;
if(prev%10==0)
prev = extra_zero(prev);

if(prev>DIGIT)
prev = truncate_digits(prev);

arr[i]=prev;

}

else if(flag[i]){

prev*=P[i];

if(prev%10==0)
prev = extra_zero(prev);

if(prev>DIGIT)
prev = truncate_digits(prev);

arr[i]=prev;

}

else{

arr[i]=arr[i-1];
}

//		printf("prev_after   %I64d\n",prev);

}

}

int main(){

seive();
to_power();
lcm();

int i,j;
//	freopen("10680.txt","rt",stdin);

while(scanf("%d",&i)==1){

if(i==0)
return 0;

j = arr[i];

j = last_digit(extra_zero(j));

printf("%d\n",j);

}
return 0;
}
``````

### Re: 10680

Posted: Sat Aug 05, 2006 3:22 am
jbh wrote:my code gives wrong output for some input like 78125. but why? plz help me.
``````397979
``6``