2
6
2
2
2
4
4
6
6
6
4
2
6
4
8
8
4
8
6
4
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;
}
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?
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]);
}
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
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;
}
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
0Code: Select all
6