Solution of ACM UVA 10551 Basic remains

Problem Statement :

Go To This statement :http://uva.onlinejudge.org/external/105/10551.html

Discussion for solution :

1. take p and m as string

2. Convert m into decimal

3. Simulate the modulo step by step using the following algorithm:

s = 0;
for (i=n; i>=0; i–) {
s *= b;
s += An;
s %= R;
}

4 .Final ans is s.

5 .Convert s into b base number

6 . critical cases :

10 1 1  ( answer 0 )
2 1 1  ( answer 0 )

——————————————————————————————————————————————————–

Code :

#include<cmath>
#include<iostream>
#include<string>
using namespace std;

long int any_base_to_decimal(int b,string  a)
{
int power=0,no;
long int gap,n=0;
for(int i=a.length()-1;i>=0;–i)
{
gap=long(pow(b,power));
no=a.at(i)-‘0′;
n+=no*gap;
++power;
}
return n;
}

void decimal_to_any_base(int b,long int n)
{
string main_string=””,another_string=””;
char ch;
ch = n%b+’0′;
main_string+=ch;
n/=b;
while( n != 0 )
{
ch = n%b+’0’;
main_string+=ch;
n/=b;
}
for(int i=main_string.length()-1;i>=0;–i)
another_string+=main_string.at(i);

cout<<another_string<<endl;
}

int main()
{
string p,m;
int b;
long int s,R;
while(1)
{
cin>>b;
if(b==0)
break;

cin>>p>>m;
R = any_base_to_decimal(b,m);
s=0;
for (int i=0;i<p.length(); i++)
{
s *= b;
s += p.at(i)-‘0’;
s %= R;
}
decimal_to_any_base(b,s);
}
return 0;
}

ACM UVA 10699 এর সম্পূর্ণ সমাধান

সুলতান আহমেদ সাগর এই সমাধানটি করেছেন ।
Theory Difficulty	easy
Coding Difficulty:	easy
Algorithms Used:	math
Solution Description:	Use the Sieve of Eratosthenes to generate all the primes up to 1,000,000. For each input, check whether each prime divides it. You don’t need to do an O(sqrt(n)) check. O(n) will do fine.

#include<iostream>
#include<cmath>
using namespace std;

#define max 1000000
int a[max];

void seieve()
{
long long int i,j,imax,jmax;
for(i=0;i<=max;i++) a[i]=1;
imax=sqrt(max)+1;
for(i=2;i<=imax;i++)
{
jmax=(max/i)+1;
if(a[i]==1)
{
for(j=2;j<=jmax;j++)
{
if(i*j<=max) a[i*j]=0;
}
}
}
}

int main()
{
seieve();
long long int i,N,temp,prime=0;
while(cin>>N && N!=0)
{
temp=N;
for(i=2;i<=N;i++)
if(N%i==0 && a[i])
{
++prime;
N/=i;
}

cout<<temp<<” : “<<prime<<endl;
prime=0;
}

return 0;
}