Firstly, you get an overflow here:jbh wrote:ok martin, i'll do that in future.
but help me on this code. i know it gives wa for some inputs.
but i can't find the problem.
Secondly, I don't believe you can do the following without loss of inportant information:seive() wrote:...for(int i=2;i*i<=size_;i++){
......if(prime[i]){
.........for(int j=i*i;j<=size_;j+=i){.........<-- here i*i is bigger than 2^31 for large i
............prime[j]=false;
.........}
......}
...}
lcm() wrote:.........if(prev>DIGIT)
.....................prev = truncate_digits(prev);.
Code: Select all
removed after ac
Code: Select all
#include<cstdio>
#include<cmath>
#include<vector>
#define max 1000000
using namespace std;
bool mark[max+10];
vector<int> prime;
void sieve()
{
int i,j,p;
for(i=2;i<=max+10;i++)
mark[i]=true;
p=(float)pow(max+10,0.5);
for(i=2;i<=p;i++)
{
if(mark[i])
for(j=i*i;j<=max+10;j=j+i)
mark[j]=false;
}
for(i=2;i<=max+10;i++)
if(mark[i])
prime.push_back(i);
i=prime[1];
prime[1]=prime[2];
prime[2]=i;
}
int main()
{
sieve();
int p2,p5,i,j,res,n,k;
while(scanf("%d",&n)!=EOF)
{
if(n==0)
break;
p2=p5=0;
for(i=2;i<=n;i=i*2)
p2++;
for(i=5;i<=n;i=i*5)
p5++;
res=1;
for(i=1;i<=(p2-p5);i++)
res=(res*2)%10;
for(i=2;prime[i]<=n;i++)
{
j=(log10(n))/log10(prime[i]);
k=(float)pow(prime[i],j);
res=(res*k)%10;
}
printf("%d\n",res);
}
return 0;
}