Showing posts with label Number Theory. Show all posts
Showing posts with label Number Theory. Show all posts
Chinese Remainder Theorem
Resources:
Chinese Remainder Theorem
Chinese Remainder Theorem ( E-Maxx)
GeeksForGeeks
forthright48 - Coprime Moduli part1
forthnight48- Non Coprime Moduli part 2
Codeforces article
Problems:
Chinese Remainder Theorem (non-relatively prime moduli)
Cheese and Random Toppings SOLUTION
1319 - Monkey Tradition SOLUTION
Number of Sequences
B. Remainders Game
Arkanoid (ark)
E. Billiard
FACT0 - Integer Factorization (15 digits)
FACT0 - Integer Factorization (15 digits)
টপিকঃ প্রাইম ফ্যাক্টর
হিন্টঃ সিভ দিয়ে করলে টাইম লিমিট, নরমালি করতে হবে। প্রথমে x = ২ দিয়ে যতবার যায় ভাগ তারপর ৩ দিয়ে , এরপর ৫ দিয়ে...
যখন x*x >N হয়ে যাবে তখন লুপটা ব্রেক হবে।
এরপর শেষে সংখ্যাটি ১ এর চেয়ে বড় থাকলে ওইটা একটা প্রাইম নাম্বার হবে, আর প্রতিবার ভাগ করার সময় একটা কাউন্ট রাখবো যেইটা দ্বারা বুঝবো ওইটা ওই প্রাইম ডিভিজর এর কাউন্ট।😀
কোডঃ
Segmented Sieve
Segmented Sieve [ Number Theory ]
Zobayer Blog
Implementation 01:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #include<bits/stdc++.h> using namespace std; #define MAX 100009 typedef long long ll; vector<int>primes; void seiveOfEratosthenes() { bool flag[MAX+1]; for(int i = 0; i <= MAX; i++) flag[i] = true; primes.push_back(2); flag[0] = flag[1] = false; for(int i = 4; i <= MAX; i += 2) flag[i] = false; for(int i = 3; i <= MAX; i += 2){ if(flag[i] == true){ // i is prime primes.push_back(i); for(int j = i+i; j <= MAX; j = j+i){ flag[j] = false; // j is not prime } } } } void segmentedSeive(ll L, ll R) { bool isPrime[R-L+1]; for(int i = 0; i <= (R-L+1); i++) isPrime[i] = true; if(L == 1)isPrime[0] = false; for(int i = 0; i < (int)primes.size() && primes[i]*primes[i] <= R; i++){ ll curPrime = primes[i]; ll base = curPrime * curPrime; if(base < L){ base = ( (L+curPrime - 1)/curPrime)*curPrime; } for(ll j = base; j <= R; j += curPrime) isPrime[j - L] = false; } for(int i = 0; i <= R - L; i++){ if(isPrime[i] == true) cout << L + i << endl; } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif double start_time = clock(); seiveOfEratosthenes(); ll L,R; cin >> L >> R; segmentedSeive(L,R); return 0; double end_time = clock(); // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |
Implementation 02:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<bits/stdc++.h> using namespace std; #define MAX 46656 #define LMT 216 #define LEN 4830 #define RNG 100032 unsigned base[MAX/64], segment[RNG/64], primes[LEN]; #define sq(x) ((x)*(x)); #define mset(x,v) memset(x,v,sizeof(x)) #define chkC(x,n) (x[n>>6]&(1<<((n>>1)&31))) #define setC(x,n) (x[n>>6]|=(1<<((n>>1)&31))) typedef long long ll; //Generates all the necessary prime numbers and marks them in base. void seive() { unsigned i,j,k; for(i = 3; i < LMT; i += 2) if(!chkC(base, i)) for(j = (i * i), k = (i << 1); j < MAX; j += k) setC(base, j); for(i = 3, j = 0; i < MAX; i += 2) if(!chkC(base, i)) primes[j++] = i; } // Returns the prime-count within range [a,b] and marks them in sement. int segmentedSeive(int a, int b) { unsigned i,j,k, cnt = (a <= 2 && 2 <= b) ? 1 : 0; if(b < 2) return 0; if(a < 3) a = 3; if(a%2 == 0)a++; mset(segment,0); for(i = 0; ( primes[i] * primes[i] ) <= b; i++){ j = primes[i] * ((a + primes[i] - 1) / primes[i]); if(j%2 == 0) j += primes[i]; for(k = (primes[i] << 1); j <= b; j += k) if(j != primes[i]) setC(segment, (j-a)); } for(i = 0; i <= (b - a); i += 2) if(!chkC(segment, i)){ cnt++; } return cnt; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif double start_time = clock(); seive(); int L,R; cin >> L >> R; cout << segmentedSeive(L,R)<<endl; return 0; double end_time = clock(); // printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |
Euler’s Phi Function
Euler’s Phi Function:
Concept:
Shoshikkha
প্রোগ্রামিং পাতা
topH
Type 01:
( যখন একসাথে অনেক গুলোর জন্য বের করতে হবে।)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include<bits/stdc++.h> using namespace std; #define MAX 2000100 typedef long long ll; ll phi[MAX]; void seivePHI(){ ll i,j; for(i = 2; i < MAX; i++){ if(phi[i] == 0){ phi[i] = i - 1; for(j = i*2; j < MAX; j += i){ if(phi[j] == 0)phi[j] = j; phi[j] /= i; phi[j] *= (i-1); } } } } int main() { /* #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif double start_time = clock();*/ int t; seivePHI(); cin >> t; for(int cs = 1; cs <= t; cs++){ int n; cin >> n; cout << "Phi("<<n<<") = "<<phi[n]<<endl; } /*double end_time = clock(); printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); */ return 0; } |
Type 02:
( যখন একটা সংখ্যার জন্য বের করতে হবে।)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<bits/stdc++.h> using namespace std; #define MAX 2000100 typedef long long ll; ll po(ll x, ll y){ ll ans = 1; while(y--) ans *= x; return ans; } ll prime(ll a) { for(ll i = 1; i*i <= a; i++){ if(a%i == 0)return 1; } return 0; } ll phi(ll n) { ll i,mul = 1, holder, fre = 0; if(prime(n) == 0) mul = n - 1; else{ for(i = 2; i*i <= n; i++){ if(n%i == 0){ while(n%i == 0){ n = n/i; holder = i; fre++; } mul *= (po(holder, fre-1)*(holder - 1)); fre = 0; } } if(n != 1){ mul *= (n-1); } } return mul; } int main() { // #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); // #endif //double start_time = clock(); ll n; cin >> n; cout << "Phi("<<n<<") = "<<phi(n)<<endl; //double end_time = clock(); //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000); return 0; } |
Problems: D. Same GCDs Solution
1014 - Ifter Party
1014 - Ifter Party
Topic: Divisor
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<bits/stdc++.h> using namespace std; typedef long long ll; set<int>V; int main() { //double start_time = clock(); #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t; cin >> t; for(int cs = 1; cs <= t; cs++){ int p,l; cin >> p >> l; int ext = p - l; int sz = sqrt(ext); // cout << ext << " "<<sz<<endl; if(l < 1)V.insert(1); if(ext > l)V.insert(ext); for(int i = 2; i <= sz; i++){ if(ext%i == 0){ if(i*i == ext){ if(i > l)V.insert(i); } else{ if(i > l)V.insert(i); if(ext/i > l)V.insert(ext/i); } } } cout << "Case "<<cs<<":"; int tt = V.size(); if(tt == 0)cout << " impossible\n"; else{ for(auto it = V.begin(); it != V.end(); it++)cout << " "<<*it; cout << endl; } V.clear(); } return 0; } |