公司动态

数学知识汇总

📅 2026/8/27 10:09:48
数学知识汇总
//判断是否是素数bool is_prime(int num){if (num 2)return false;for (int i 0; i num / i; i){if (num % i 0)return false;}return true;}//判断素数的个数vectorboolstatus;int cnt;vectorintprime;void cnt_prime(int num){prime.resize(num 1, true);prime[0] prime[1] false;for (int i 2; i num; i){if (status[i]){cnt;prime.push_back(i);for (int j 0; j prime.size() prime[j] num / i; j){status[prime[j] * i] false;if (i % prime[j] 0)break;}}}}//分解质因数vectorintans;void prime_divide(int num){for (int i 2; i num; i){if (num % i 0){ans.push_back(i);while (num % i 0){num / i;}}}if (num 1)ans.push_back(num);}//分解因数vectorintans;void get_divisors(int num){for (int i 1; i num / i; i){if (num % i 0){ans.push_back(i);if (i ! num / i)ans.push_back(num / i);}}}//计算因数个数unordered_mapint, intall;int cnt;typedef long long ll;const int mod 1e9 7;ll count(int num){for (int i 2; i num / i; i){if (num % i 0){while (num % i 0){all[i];cnt;}}}if (num 1)all[num];ll result 0;for (auto i : all){result result * (i.second 1) % mod;}return result;}//计算因数之和unordered_mapint, intall;int cnt;typedef long long ll;const int mod 1e9 7;ll sum(int num){for (int i 2; i num / i; i){if (num % i 0){while (num % i 0){all[i];cnt;}}}if (num 1)all[num];ll result 0;for (auto cnt : all){int p cnt.first;int a cnt.second;ll t 1;for (int i 0; i a; i){t (t * p 1) % mod;}result result * t % mod;}return result;}//欧拉函数,即计算小于n有多少数和n互质int Euler(int num){int ans 0;for (int i 2; i num / i; i){if (num % i 0){ans ans / i * (i - 1); //对应公式ans*(1-1/i)while (num % i 0)num / i;}}if (num 1)ans ans / num * (num - 1);return ans;}//线性筛求欧拉函数即求范围内每个数的欧拉函数值vectorintphi;vectorintprime;vectorboolis_prime;typedef long long ll;ll Euler(int num){phi.resize(num 1, 1);is_prime.resize(num 1, true);for (int i 2; i num; i){if (is_prime[i]){prime.push_back(i);phi[i] i - 1;}for (int j 0; j prime.size() prime[j] num / i; j){is_prime[prime[j] * i] false;if (i % prime[j] 0){phi[prime[j] * i] prime[j] * phi[i];break;}phi[prime[j] * i] (prime[j] - 1) * phi[i];}}ll ans 0;for (auto curr : phi)ans curr;return ans-1; //不要index0}//求逆元//逆元的充要条件是am互质如果m是质数则可以用ksp求否则只能用exgcd求typedef long long ll;ll ksp(ll n, ll p, ll mod){ll ans 1;while (p){if (p 1)ans ans * n % mod;p 1;n n * n % mod;}return ans % mod;}ll gcd(ll a, ll b){return b 0 ? a : gcd(b, a % b);}int main(){int n;cin n;while (n--){ll n, p;cin n p;if (gcd(n, p) ! 1)cout impossible endl;elsecout ksp(n, p - 2, p)endl;}}//扩展欧几里得例题求线性同余方程typedef long long ll;int exgcd(int a, int b, int x, int y){if (b 0){x 1, y 0;return a;}int d exgcd(b, a % b, y, x);y - a / b * x;return d;}int main(){int n;cin n;while (n--){int a, b, m;cin a b m;int x, y 0;int d exgcd(a, m, x, y);if (b % d)cout impossible endl;elsecout (ll)x * (b / d) % m endl;;}return 0;}