10680 - LCM
Moderator: Board moderators
10680 can u help
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
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
25
125
625
3125
15625
78125
390625
1. generate all primes upto 10^6
2. generate all powers of each prime
3. calculate the lcm using the following
Any thoughts regarding the algorithm I am using?
Regards,
Suman.
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;
}
}
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;
}
Regards,
Suman.
10680 - TLE! Why?
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);
}
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);
}
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: 10680 - TLE! Why?
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.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;
..}
LCM of two numbers is: lcm(a,b) = a*b/gcd(a,b).scidong wrote:How can i calculate LCM?
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.
-
- New poster
- Posts: 7
- Joined: Fri Mar 31, 2006 1:22 pm
10680 WA
Can anyone say where is wrong?
I try to solve it but fault
I try to solve it but fault
![:(](./images/smilies/icon_frown.gif)
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]);
}
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: 10680 WA
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.a123123123888 wrote:Can anyone say where is wrong?
I try to solve it but fault![]()
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: 10680 WA
and btw, if there is a thread on a particular problem, please, use that thread and do not create a new one.
10680
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;
}
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: 10680
Your solution isn't working for:jbh wrote:my code gives wrong output for some input like 78125. but why? plz help me.
Code: Select all
397979
0
Code: Select all
6