今天突然想复习一下数论,也就顺便整理了一下关于数论的基础知识,
以后用的时候直接用就行了,也不用现敲了,其实就是有点懒。。。。
以后用的时候直接用就行了,也不用现敲了,其实就是有点懒。。。。
具体解释都在代码里有解释
直接上代码了:
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #include <queue> #include <algorithm> #include <set> using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long LL; typedef unsigned long long ULL; const int maxn = 1e4+5; const int mod = 1000000007; const double eps = 1e-7; bool prime[maxn]; int p[maxn],k; ///素数筛选 void isprime() { k = 0; MM(prime); for(int i=2; i<maxn; i++) { if(!prime[i]) { p[k++] = i; for(int j=i*i; j<maxn; j+=i) prime[j] = 1; } } } int fac[maxn], num[maxn], cnt; ///分解素因子算法 void Dec(int x) { MM(num); cnt = 0; for(int i=0; p[i]*p[i]<=x&&i<k; i++) { if(x%p[i] == 0) { fac[cnt] = p[i]; while(x%p[i] == 0) { num[cnt]++; x /= p[i]; } cnt++; } } if(x > 1) { fac[cnt] = x; num[cnt++] = 1; } } ///欧拉公式的延伸:一个数的所有质因子之和是euler(n)*n/2 int Euler(int m) { int ret = m; for(int i=2; i*i<=m; i++) { if(m%i == 0) ret -= ret/i; while(m%i == 0) m /= i; } if(m > 1) ret -= ret/m; return ret; } ///最大公约数 LL gcd(LL x, LL y) { if(y == 0) return x; return gcd(y, x%y); } ///扩展欧几里得算法 void exgcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1; y = 0; return; } exgcd(b, a%b, x, y); LL tmp = x; x = y; y = tmp-(a/b)*y; } int main() { int m, t; //isprime(); cin>>t; while(t--) { ///素因子分解 /** cin>>m Dec(m); for(int i=0; i<cnt-1; i++) for(int j=0; j<num[i]; j++) cout<<fac[i]<<'*'; for(int i=0; i<num[cnt-1]-1; i++) cout<<fac[cnt-1]<<"*"; cout<<fac[cnt-1]<<endl; **/ ///欧拉函数 /**cout<<Euler(m)<<endl;**/ ///扩展欧几里得算法 /** LL a, b, x, y; cin>>a>>b; if(gcd(a,b) != 1)///没有解 { puts("Sorry"); continue; } exgcd(a, b, x, y); x = (b + x % b) % b; y = (1 - a * x) / b; cout<< x << " " << y << endl; **/ } return 0; }