Skip to content

Instantly share code, notes, and snippets.

@dipta10

dipta10/SPOJ COMDIV.cpp

Last active November 7, 2018 16:31
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save dipta10/4ce01ffc59460bc165d912e1fa416d5d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save dipta10/4ce01ffc59460bc165d912e1fa416d5d to your computer and use it in GitHub Desktop.
Download ZIP
Number Theory Review #1 by Solving SPOJ, UVA Problems (Bangla | বাংলা)
Raw
SPOJ COMDIV.cpp
/*
* link: https://www.spoj.com/problems/COMDIV/
* HINT: USE scanf, printf or use fast I/O
* HINT: numberOfCommonDiv = numberOfCommonDiv(gcd(n1, n2))
* You can use __gcd(), it will work in GNU.
* You will be given T (T<=10^6) pair of numbers. All you have to tell is the number of common divisors between two numbers in each pair.
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int getDiv(int n) {
int ans = 0;
for (int i = 1; i * i <= n; ++i) {
if (i * i == n) ans += 1;
else if (n % i == 0) ans += 2;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
// freopen("input", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t, a, b;
cin >> t;
while (t--) {
cin >> a >> b;
int x = gcd(a, b);
cout << getDiv(x) << "\n";
}
return 0;
}
Raw
SPOJ DIV Divisors.cpp
/*
* SPOJ DIV - Divisors
* link: https://www.spoj.com/problems/DIV/
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef unsigned long long ull ;
const int mx = 1000000 ;
int cnt ;
int divisor[mx+10] ;
vector <int> prime_factor[mx+10] ;
void sieve()
{
for(int i=1;i<=mx;i++)
{
for(int j=i;j<=mx;j+=i) divisor[j]++;
}
for(int i=2;i<=mx;i++)
{
if(prime_factor[i].size()==0)
{
for(int j=i;j<=mx;j+=i) prime_factor[j].push_back(i);
}
}
}
int main()
{
sieve();
for(int i=1;i<=mx;i++)
{
int x = divisor[i] ;
if(prime_factor[x].size()==2&&prime_factor[x][0]*prime_factor[x][1]==x)
{
cnt++;
if(cnt%9==0) printf("%d\n", i);
}
}
return 0;
}
Raw
SPOJ DIVSUM - Divisor Summation.cpp
/*
* link: https://www.spoj.com/problems/DIVSUM/
*/
#include <bits/stdc++.h>
using namespace std;
int sol (int n) {
if (n < 2) return 0;
int cnt = 1;
for (int i = 2; i * i <= n; ++i) {
if (i*i == n) cnt += i;
else if (n % i == 0) cnt += i, cnt += (n/i);
}
return cnt;
}
int main()
{
// freopen("input", "r", stdin);
int t, x; cin >> t;
while (t--) {
cin >> x;
cout << sol(x) << endl;
}
return 0;
}
Raw
UVA 10392 - Factoring Large Numbers.cpp
/*
* UVA 10392 Factoring Large Numbers
* https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1333
*/
#include <bits/stdc++.h>
#define filein freopen("input", "r", stdin)
using namespace std;
using ll = long long;
bitset<10000007> bs;
vector<ll> prime;
void sieve(long long upper_bound) {
bs.set();
bs[0] = bs[1] = 0;
prime.push_back(2);
for(ll i = 3; i <= upper_bound + 1; i += 2) {
// using upper_bound + 1 just for the safety as discussed
// in our previous tutorials
if(bs[i]) {
for(ll j = i * i; j <= upper_bound + 1; j += i)
bs[j] = 0;
prime.push_back(i);
}
}
}
void primeFactorize( ll n ) {
for( int i = 0; prime[i] * prime[i] <= n; i++ ) {
if( n % prime[i] == 0 ) {
while( n % prime[i] == 0 ) {
n /= prime[i];
cout << " " << prime[i] << endl;
}
}
}
if (n > 1) cout << " " << n << endl;
}
int main() {
// filein;
sieve(10000007);
ll x;
while (scanf("%lld", &x) && x != -1) {
if (x < 0) x *= (-1);
primeFactorize(x);
cout << endl;
}
return 0;
}
Raw
UVA 11466 - Largest Prime Divisor.cpp
/*
* https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9
* Long Long -> Max Digit = 19, Int -> Max Digit = 10
* Max size of global array can be upto 10^8, though I'm using 10^7
*/
#include <bits/stdc++.h>
#define filein freopen("input", "r", stdin)
using namespace std;
using ll = long long;
ll List[10000007];
int listSize;
bitset<10000007> bs;
vector<ll> prime;
void sieve(long long upper_bound) {
bs.set();
bs[0] = bs[1] = 0;
prime.push_back(2);
for(ll i = 3; i <= upper_bound + 1; i += 2) {
// using upper_bound + 1 just for the safety as discussed
// in our previous tutorials
if(bs[i]) {
for(ll j = i * i; j <= upper_bound + 1; j += i)
bs[j] = 0;
prime.push_back(i);
}
}
}
void primeFactorize( ll n ) {
listSize = 0;
for( int i = 0; prime[i] * prime[i] <= n; i++ ) {
if( n % prime[i] == 0 ) {
List[listSize] = prime[i];
listSize++;
while( n % prime[i] == 0 ) {
n /= prime[i];
}
}
}
if( n > 1 ) {
List[listSize] = n;
listSize++;
}
if (listSize > 1) {
cout << List[listSize-1] << endl;
} else {
cout << "-1" << endl;
}
}
int main() {
// filein;
sieve(10000007);
ll x;
while (scanf("%lld", &x) && x != 0) {
if (x < 0) x *= (-1);
primeFactorize(x);
}
return 0;
}
/* Sample Test Case
* input
1000
20
32
1
-1
-10
61536575712
8172385155
90090
12
199900
-26356
-32
8748234
23462482
23457826407
234872648001
436598
345387
2347
17
37
0
* output:
5
5
-1
-1
-1
5
324889
16509869
13
3
1999
599
-1
113
690073
77418569
348559
521
16447
-1
-1
-1
*/
Raw
UVA 11960 Divisor Game.cpp
/*
* Name: UVA 11960 Divisor Game
* link: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3111
*/
#include <bits/stdc++.h>
using namespace std;
#define mx 1000006
int divs[mx+10];
int ans[mx+10];
void sieve() {
for (int i = 1; i <= mx; ++i) divs[i] = 2;
divs[1] = 1;
for (int i = 2; i <= mx; ++i) {
for (int j = 2*i; j <= mx; j += i) {
divs[j]++;
}
}
ans[1] = 1;
for (int i = 2; i <= mx; ++i) {
if (divs[i] >= divs[ans[i-1]]) {
ans[i] = i;
} else {
ans[i] = ans[i-1];
}
}
}
int main() {
//freopen("input.txt", "r", stdin);
sieve();
int t;
int x;
cin >> t;
while (t--) {
cin >> x;
cout << ans[x] << endl;
}
//for (int i = 0; i < 10; ++i) cout << divs[i] << " ";
//puts("");
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment