标签：prime 2024.11 return 14 int ll long 质因数
数论
一、快速幂
#include<iostream>
using namespace std;
int fastPow(int a, int n){
int ans = 1;
while (n)
{
if(n&1) ans = ans * a;
a *= a;
n >>= 1;
}
return ans;
}
typedef long long ll;
ll fastPow(ll a, ll n, ll m){
ll ans = 1;
a %= m;
while(n){
if(n&1) ans = (ans * a) % m;
a = (a * a) % m;
n >>= 1;
}
return ans;
}
int main(){
return 0;
}
二、高斯消元
#include<iostream>
using namespace std;
double a[105][105];
double eps = 1e-7;
int main(){
int n;
cin>>n;
for(int i=1; i<=n; i++){
for(int j=1; j<=n+1; j++){
cin>>a[i][j];
}
}
//枚举列
for(int i=1; i<=n; i++){
//枚举行，选一个非零系数，这里选最大的系数
int max = i;
for(int j=i+1; j<=n; j++){
if(abs(a[j][i]) > abs(a[max][i])) max = j;
}
//交换两行
for(int j=1; j<=n+1; j++){
swap(a[i][j], a[max][j]);
}
//如果对角线上主元系数为0，说明无唯一解
if(abs(a[i][i]) < eps){
cout<<"No Solution"<<endl;
return 0;
}
//把这一行的主元系数变为1
for(int j=n+1; j>=1; j--){
a[i][j] = a[i][j] / a[i][i];
}
//消去主元所在列的其他行的主元
for(int j=1; j<=n; j++){
if(j != i){
double tmp = a[j][i] / a[i][i];
for(int k=1; k<=n+1; k++){
a[j][k] -= a[i][k] * tmp;
}
}
}
}
for(int i=1; i<=n; i++){
printf("%.2lf\n", a[i][n+1]);
}
return 0;
}
三、取模运算
#include<iostream>
using namespace std;
//乘法取模: (a * b) % m
long long mul(long long a, long long b, long long m){
a = a % m;
b = b % m;
long long res = 0;
while(b){
if(b&1) res = (res + a) % m;
a = (a * 2) % m;
b >>= 1;
}
return res;
}
int main(){
long long a = 0x7877665544332211;
long long b = 0x7988776655443322;
//若m大于a，mul()会出错
long long m = 0x998776655443322;
cout<<mul(a, b, m)<<endl;
cout<<"错误的："<<((a % m) * (b % m)) % m<<endl;
return 0;
}
四、素数
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
//一、小素数的判定：试除法
bool is_prime(long long n){
if(n <= 1) return false;
for(long long i = 2; i <= sqrt(n); i++){
if(n % i == 0) return false;
}
return true;
}
//二、大素数的判定：Miller-Rabin素性测试
typedef long long ll;
//快速幂取模 x^y % m
ll fastPow(ll x, ll y, int m){
ll res = 1;
x %= m;
while (y)
{
if(y&1) res = (res * x) % m;
x = (x * x) % m;
y >>= 1;
}
return res;
}
//Miller-Rabin素性测试 返回true表示n是合数
bool witness(ll a, ll n){
//u： n-1 的二进制去掉末尾0
ll u = n - 1;
//n-1的二进制，是奇数u的二进制后面加t个0
int t = 0;
//整数n-1末尾0的个数就是t
while(u&1 == 0){
u >>= 1;
t++;
}
ll x1, x2;
//a^u % n
x1 = fastPow(a, u, n);
//做t次平方取模
for(int i=1; i<=t; i++){
x2 = fastPow(x1, 2, n);
if(x2 == 1 && x1 != 1 && x1 != n-1){
return true;
}
x1 = x2;
}
//用费马测试判断是否为合数
if(x1 != 1) return true;
return false;
}
//对n做s次测试
int Miller_Rabin(ll n, int s){
if(n < 2) return 0;
if(n == 2) return 1;
if(n % 2 == 0) return 0;
for(int i=0; i<s && i<n; i++){
//基值a是随机数
ll a = rand() % (n-1) + 1;
if(witness(a, n)) return 0;
}
return 1;
}
int main01(){
int m;
while(cin>>m){
int cnt = 0;
for(int i=0; i<m; i++){
ll n;
cin>>n;
int s = 50;
cnt += Miller_Rabin(n, s);
}
cout<<cnt<<endl;
}
return 0;
}
//三、素数筛
//1.埃氏筛
const int N = 1e7;
int prime[N+1];
//如果visit[i] = true 表示它被筛掉了，不是素数
bool visit[N+1];
//求[2,n]内素数
int E_sieve(int n){
//初始化
memset(visit, 0, sizeof(visit));
for(int i=2; i<=sqrt(n); i++){
if(!visit[i]){
//i是素数，i的倍数都不是素数
//j小于i的情况前面已经试过了
for(int j=i*i; j<=n; j+=i){
visit[j] = true;
}
}
}
//记录素数
int sum = 0;
for(int i=2; i<=n; i++){
if(!visit[i]) prime[sum++] = i;
}
return sum;
}
//2.欧拉筛
//int prime[N+1];
//bool visit[N+1];
int euler_sieve(int n){
memset(visit, 0, sizeof(visit));
int sum = 0;
for(int i=2; i<=n; i++){
if(!visit[i]) prime[sum++] = i;
//用已经得到的素数去筛数
for(int j=0; j<sum; j++){
//只筛小于或等于n的数
if(i * prime[j] > n) break;
//用x的最小质因数筛去x，prime[j]是x的最小质因数
visit[i * prime[j]] = true;
//i%prime[j]==0 意味着i可以被分解出更小的质因数
//i已经不是x的最小质因数，不能再往后筛了
if(i % prime[j] == 0) break;
}
}
return sum;
}
//四、质因数分解
//1.用欧拉筛求最小质因数
//int prime[N+1];
//visit[]记录最小质因数
int vis[N+1];
int factor_used_euler_sieve(int n){
memset(vis, 0, sizeof(vis));
int sum = 0;
for(int i=2; i<=n; i++){
if(!vis[i]){
vis[i] = i;
prime[sum++] = i;
}
//用已经得到的素数去筛数
for(int j=0; j<sum; j++){
//只筛小于或等于n的数
if(i * prime[j] > n) break;
//用x的最小质因数筛去x，prime[j]是x的最小质因数
vis[i * prime[j]] = prime[j];
//i%prime[j]==0 意味着i可以被分解出更小的质因数
//i已经不是x的最小质因数，不能再往后筛了
if(i % prime[j] == 0) break;
}
}
return sum;
}
//2.用试除法分解质因数
//p[]记录因数，p[1]是最小因数，一个int型数的质因数最多十几个
int p[20];
//c[]记录第i个因数的个数，一个因数的个数最多三十几个
int c[40];
int factor(int n){
//质因数的个数
int sum = 0;
for(int i=2; i<=sqrt(n); i++){
if(n % i == 0){
p[++sum] = i;
c[sum] = 0;
//把n重复的因数去掉
while(n % i == 0){
n /= i;
c[sum]++;
}
}
}
//没除尽，n是素数
if(n > 1){
p[++sum] = n;
c[sum] = 1;
}
return sum;
}
//3.用pollard_rho启发式方法分解质因数
typedef long long ll;
//确保输入大于等于0
ll gcd(ll a, ll b){
return b ? gcd(b, a%b) : a;
}
//(a * b) % n
ll mul_mod(ll a, ll b, ll n){
a %= n;
ll ret = 0;
while(b){
if(b&1){
ret += a;
if(ret >= n) ret -= n;
}
a <<= 1;
if(a >= n) a -= n;
b >>= 1;
}
return ret;
}
//返回一个因数，不一定是质因数
ll pollard_rho(ll n){
ll i=1, k=2;
ll c = rand() % (n-1) + 1;
ll x = rand() % n;
ll y = x;
while (true)
{
i++;
x = (mul_mod(x, x, n) + c) % n;
ll d = gcd(y>x ? y-x : x-y, n);
if(d!=1 && d!=n) return d;
if(y == x) return n;
if(i == k){
y = x;
k <<= 1;
}
}
}
ll fac[N];
int tol;
//找到所有的质因数
void findfactors(ll n){
//判断是否为素数
if(Miller_Rabin(n, 50)){
fac[tol++] = n;
return;
}
ll p = n;
while(p >= n){
//找到一个因数
p = pollard_rho(p);
}
//继续寻找更小的因数
findfactors(p);
findfactors(n / p);
}
int main(){
return 0;
}
标签：prime,
2024.11,
return,
14,
int,
ll,
long,
质因数
From： https://blog.csdn.net/a7i72/article/details/143783531