/*
user: php
time: 0.308 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1240
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAXX 15811
#define SZ 9752
int primes[SZ];
bool isPrime[MAXX];
void genaratePrime()
{
//let think n'th index reprent the number 2n+1
for(int i=1; i<MAXX; i++) isPrime[i] = true;
for(long long int i=1; i<MAXX; i++)
{
if(isPrime[i])
{
for(long long int j=4*i*i + 4*i + 1; j<MAXX; j += 4*i + 2)
{
isPrime[j>>1] = false;
}
}
}
int p=0;
primes[p++] = 2;
for(int i=1; i<MAXX; i++)
{
if(isPrime[i])
{
primes[p++] = (i<<1) + 1;
}
}
primes[p] = 1000000005;
}
int main()
{
genaratePrime();
int input, count, root, limit, temp;
while(true)
{
scanf("%d", &input);
if(input == 0 ) break;
if(input == 1)
{
printf("0\n");
}
else if(input == 2 )
{
printf("1\n");
}
else
{
count = input ;
root = sqrt(input) + 1;
for(int i=0; primes[i] < root && input != 1; i++)
{
if(input % primes[i] == 0)
{
count -= count/primes[i];
do
{
input /= primes[i];
}while(input % primes[i] == 0);
}
}
if(input > 1) count -= count / input;
printf("%d\n", count);
}
}
}
Monthly Archives: December 2012
(UVa) 884 – Factorial Factors
1when I make “countFactorialFactor()” function with recursion it causes RunTimeError. It may cause for calling a function huge times … I don’t know the actual cause đĻ
/*
user: php
time: 0.104 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=825
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define MAXX 1000001
#define loop(i, n) for(int i=0; i<n; i++)
#define loop1(i, n) for(int i=1; i<n; i++)
#define SZ 78499
int listOfPrimes[SZ];
bool isPrime[MAXX];
int numberOfFactors[MAXX];
int dp[MAXX];
void genaratePrimes()
{
int rootN = sqrt(MAXX) + 1;
loop1(i, MAXX)
{
if(i%2 == 0) isPrime[i] = false;
else isPrime[i] = true;
}
isPrime[2] = true;
for(int i=3; i<rootN; i +=2)
{
if(isPrime[i])
{
for(int j=i*i; j<MAXX; j += 2*i)
{
isPrime[j] = false;
}
}
}
listOfPrimes[0] = 2;
int p = 1;
for(int i=3; i<MAXX; i++)
{
if(isPrime[i])
{
listOfPrimes[p++] = i;
}
}
listOfPrimes[p] = 1000009; //dummy number
}
int rec(int n)
{
if(numberOfFactors[n] != -1) return numberOfFactors[n];
if(isPrime[n]) return numberOfFactors[n] = 1;
int root = sqrt(n) + 1;
int i;
for(i=0; listOfPrimes[i] < root; i++)
{
if(n % listOfPrimes[i] == 0)
{
break;
}
}
numberOfFactors[n] = 1 + rec(n / listOfPrimes[i]);
}
void countFactorialFactor()
{
dp[2] = numberOfFactors[2];
for(int i=3; i<MAXX; i++)
{
dp[i] = numberOfFactors[i] + dp[i-1];
}
}
int main()
{
genaratePrimes();
loop(i, MAXX)
{
numberOfFactors[i] = -1;
dp[i] = -1;
}
for(int i=2; i<MAXX; i++)
{
rec(i);
}
countFactorialFactor();
int input;
int root;
int count;
long long int divisor, vagfol;
while(scanf("%d", &input) == 1)
{
printf("%d\n", dp[input]);
}
return 0;
}
(UVa) 10780 – Again Prime? No Time.
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1721
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define getint(a) scanf("%d", &a)
using namespace std;
#define MAXX 5000
#define SIZE 669
int primes[SIZE];
bool isPrime[MAXX];
int indicator, m;
void genaratePrimes()
{
int p = 0;
isPrime[2] = true;
for(int i=3; i<MAXX; i++)
{
if(i%2 == 0) isPrime[i] = false;
else isPrime[i] = true;
}
int root = sqrt(MAXX) + 1;
for(int i=3; i<root; i++)
{
if(isPrime[i])
{
for(int j=i*i; j<MAXX; j += 2*i)
{
isPrime[j] = false;
}
}
}
for(int i=2; i<MAXX; i++)
{
if(isPrime[i])
{
primes[p++] = i;
}
}
}
int nextprime()
{
while(m % primes[indicator] != 0)
{
indicator++;
}
return primes[indicator];
}
int findpower(int prime)
{
int count = 0;
while(m % prime == 0)
{
count++;
m = m/prime;
}
return count;
}
void findPrimeandPower( int &prime, int &power)
{
prime = nextprime();
power = findpower(prime);
}
int findMaxPower(int num)
{
int p, pow, temp, t, count = 0;
findPrimeandPower(p, pow);
t = p;
while(true)
{
temp = num / t;
if(temp == 0) break;
count += temp;
t *= p;
}
count /= pow;
return count;
}
int main()
{
genaratePrimes();
int kases, n, result, kaseno = 0, temp;
getint(kases);
while(kases--)
{
getint(m);
getint(n);
result = 10000000;
indicator = 0;
while(m != 1)
{
temp = findMaxPower(n);
if(temp < result)
{
result = temp;
}
}
printf("Case %d:\n", ++kaseno);
if(result)
{
printf("%d\n", result);
}
else
{
printf("Impossible to divide\n");
}
}
return 0;
}
(UVa) 294 – Divisors
0I misspelled the “divisisorts” but, I’m too lazy to make it “divisors”. The array indicates that how many divisors a number has.
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=230
*/
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXX 10001
#define loop(i, n) for(int i=0; i<n; i++)
int divisisorts[MAXX];
int main()
{
int kases, diff, maxDivisisors;
long long lower, upper, lower_limit, i, j, temp, which;
double upper_limit;
scanf("%d", &kases);
while(kases--)
{
maxDivisisors = -1;
scanf("%lld %lld", &lower, &upper);
diff = upper - lower;
for(int i=0; i<= diff; i++)
{
divisisorts[i] = 0;
}
upper_limit = sqrt(upper);
for(i=1; i<=upper_limit; i++)
{
temp = ceil((long double)lower / (long double)i ) ;
if(temp <= i)
{
temp = i+1;
divisisorts[i*i-lower]++;
}
j = temp*i - lower;
for(; j<=diff; j += i)
{
divisisorts[j] += 2;
}
}
for(i=lower; i<=upper; i++)
{
if(maxDivisisors < divisisorts[i - lower])
{
maxDivisisors = divisisorts[i-lower];
which = i;
}
}
printf("Between %lld and %lld, %lld has a maximum of %d divisors.\n", lower, upper, which, maxDivisisors);
}
return 0;
}
(UVa) 12015 – Google is Feeling Lucky
0
/*
user: php
time: 0.012 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3166
*/
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
int main()
{
string topList[10], str;
int p, kases, kaseno = 0, rank, maxRank;
scanf("%d", &kases);
while(kases--)
{
maxRank = -1;
for(int i=0; i<10; i++)
{
cin>>str>>rank;
if(rank == maxRank)
{
topList[p++] = str;
}
else if(rank > maxRank)
{
maxRank = rank;
p = 0;
topList[p++] = str;
}
}
printf("Case #%d:\n", ++kaseno);
for(int i=0; i<p; i++)
{
cout<<topList[i]<<endl;
}
}
return 0;
}
(UVa) 10789 – Prime Frequency
0
/*
user: php
time: 0.024 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1730
*/
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
#define MAXX 2001
#define SIZE 168
#define loop(i, n) for(int i=0; i<n; i++)
int primes[SIZE];
bool isPrime[MAXX];
void genaratePrimes()
{
int p = 0;
isPrime[0] = false;
isPrime[1] = false;
for(int i=2; i<MAXX; i++)
isPrime[i] = true;
for(int i=2; i<1001; i++)
{
if(isPrime[i])
{
primes[p++] = i;
for(int j=2*i; j<MAXX; j += i)
{
isPrime[j] = false;
}
}
}
}
int main()
{
genaratePrimes();
int numbers[10], bigAlphabet[26], smallAlphabet[26];
int kases, len, kaseno = 0;
string str;
bool flag;
scanf("%d", &kases);
while(kases--)
{
loop(i, 10) numbers[i] = 0;
loop(i, 26)
{
smallAlphabet[i] = 0;
bigAlphabet[i] = 0;
}
flag = false;
cin>>str;
len = str.size();
loop(i, len)
{
if('0'<= str[i] && str[i] <= '9')
{
numbers[str[i] - '0']++;
}
else if('a' <= str[i] && str[i] <= 'z')
{
smallAlphabet[str[i]-'a']++;
}
else
{
bigAlphabet[str[i] - 'A']++;
}
}
printf("Case %d: ", ++kaseno);
loop(i, 10)
{
if(isPrime[numbers[i]])
{
flag = true;
printf("%d", i);
}
}
loop(i, 26)
{
if(isPrime[bigAlphabet[i]])
{
flag = true;
printf("%c", i+'A');
}
}
loop(i, 26)
{
if(isPrime[smallAlphabet[i]])
{
flag = true;
printf("%c", i+'a');
}
}
if(!flag)
{
printf("empty");
}
printf("\n");
}
}
(UVa) 543 – Goldbach’s Conjecture
0
/*
user: php
time: 0.052 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=484
*/
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXX 1000000
#define loop(i, n) for(int i=0; i<n; i++)
#define SIZE 78498
int primes[SIZE];
bool isPrime[MAXX];
void genaratePrimes()
{
int p = 0;
loop(i, MAXX)
isPrime[i] = true;
for(int i=2; i<1001; i++)
{
if(isPrime[i])
{
primes[p++] = i;
for(int j=2*i; j<MAXX; j += i)
{
isPrime[j] = false;
}
}
}
}
int main()
{
genaratePrimes();
loop(i, SIZE)
{
isPrime[primes[i]] = true;
}
int number, temp;
bool possible;
while(true)
{
possible = false;
scanf("%d", &number);
if(number == 0)
{
break;
}
loop(i, SIZE)
{
temp = number - primes[i];
if(isPrime[temp])
{
printf("%d = %d + %d\n", number, primes[i], temp);
possible = true;
break;
}
}
if( ! possible )
{
printf("Goldbach's conjecture is wrong.\n");
}
}
}
(UVa) 10699 – Count the factors
0
/*
user: php
time: 0.012 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1640
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<map>
#define loop(i, n) for(int i=0; i<n; i++)
using namespace std;
int primes[168] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};
bool mp[168];
int position, count;
void recFindDivisisors(int n)
{
if(n==1)
{
return;
}
if(position > 167)
{
count++;
return;
}
if(n % primes[position] == 0)
{
if( ! mp[position] )
{
mp[position] = true;
count++;
n = n / primes[position];
recFindDivisisors(n);
}
else
{
n = n / primes[position];
recFindDivisisors(n);
}
}
else
{
position++;
recFindDivisisors(n);
}
}
int main()
{
int number;
while(true)
{
scanf("%d", &number);
if(number == 0) break;
loop(i, 168) mp[i] = false;
count = position = 0;
recFindDivisisors(number);
printf("%d : %d\n", number, count);
}
}
(UVa) 10110 – Light, more light
0
/*
user: php
time: 0.028 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1051
*/
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
double root;
long long int input;
while(true)
{
scanf("%lld", &input);
if(input == 0 ) break;
root = sqrt(input);
input = (int)root;
if(root==input)
{
printf("yes\n");
}
else
{
printf("no\n");
}
}
return 0;
}
(UVa) 900 – Brick Wall Patterns
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=841
*/
#include<iostream>
#include<cstdio>
using namespace std;
long long int dp[51];
long long int rec(int n)
{
if(dp[n] != -1) return dp[n];
return dp[n] = rec(n-1) + rec(n-2);
}
int main()
{
for(int i=2; i<51; i++)
{
dp[i] = -1;
}
dp[0] = 1;
dp[1] = 1;
int n;
while(true)
{
scanf("%d", &n);
if(n == 0) break;
printf("%lld\n", rec(n));
}
}
UnLucky Codes 