Introduction
Those who know me are aware that I am a JR (Konjac) who is not good at math, and I have never passed a math exam… Hence, this article was created.
01Recap
You know bitwise operations, right? You know high precision, right? You know binary, right? If so, let’s move on!
02Fast Exponentiation, Light Speed Exponentiation
Binary Exponentiation is a small trick to compute a^n in O(logn) time, while brute force calculation requires O(n) time. When a^n is very large, brute force is not applicable, but this situation requires the output to be modulo some number, so we need a method that ensures the answer is within 0 to mod-1 and keeps the time complexity acceptable. Fast exponentiation is an algorithm based on the divide-and-conquer principle to solve this problem.The code is simple and based on the binary idea: int qpow(int a,int b){ int res=1; while(b){ if(b&1)res*=a,res%=mod; // Check if the current binary bit is 1 a*=a;a%=mod; b>>=1; } return res%mod;} It is very fast, O(logn), as can be verified by the master theorem.However, the real problem is quite tricky. Given a positive integer x and n positive integers ai, we need to compute x^a mod p. Clearly, this cannot be done directly, leading to the concept of light speed exponentiation, which is applicable when the base and modulus are constant, and preprocessing the exponent is faster, O(n), which is evidently less than O(nlogn): int k=sqrt(mod);int l[N],h[N];void lpow(int x){// Base x l[0]=h[0]=1; for(int i=1;i<=k;i++) l[i]=l[i-1]*x%mod; for(int i=1;i<=k;i++) h[i]=h[i-1]*l[k]%mod;} void solve(){ int x,n; cin>>x>>n; // Base x and number of queries n lpow(x); while(n--){ int c; cin>>c; // Query for x raised to the power c cout<<h[c/k]*l[c%k]%mod<<' '; }} Why is this feasible? Because n^k=n^(floor(n/floor(√n))*floor(√n))*n^(k-(floor(n/floor(√n))*floor(√n)).03Prime Factorization
How to find the greatest common divisor? Using the Euclidean algorithm! int gcd(int a,int b) { while (b!=0) { int tmp=a; a=b; b=tmp%b; } return a;} We want to know how many prime numbers are less than or equal to n, which can be done using a linear sieve with a time complexity of O(n): vector<int> f;bool not_prime[N];void pre(int n) { for (int i=2;i<=n;++i) { if (!not_prime[i]) { f.push_back(i); } for (int j: f) { if (i*j>n) break; not_prime[i*j]=true; if (i %j==0) { This means i has been filtered by j before. Since the primes in f are in ascending order, the result of i multiplied by other primes will definitely be filtered out by j's multiples, so there is no need to filter again here. Therefore, we can break out of the loop here. break; } } }}This is the basic content; I will add more next time.
See you next time,ヾ(￣▽￣)Bye~Bye~Previous quality content from the public account:Beginner C++ Programming Lecture 1: Greedy AlgorithmBeginner Scratch Programming Lecture 1: Gravity and ReboundAn Interesting ExperimentBeginner C++ Programming Lecture 6: Structures