数学公式

1 + 1+2 + 1+2+3 + 1+2+3+4 + ······ + 1+2+3+···+n = $\frac{n*(n+1)*(n+2)}{6}$

$1^2$ + $2^2$ + $3^2$ + ······ + $n^2$ = $\frac{n*(n+1)*(2n+1)}{6}$

$1 + \frac{1}{2} + \frac{1}{3} + ··· + \frac{1}{n - 1} = In(n) + 0.5772156649$(约等于， n越大误差越小)

欧拉筛

int isprime[N];
vector<int> prime;
void sieve()
{
	for (int i = 2; i < N; i++)
		isprime[i] = 1;
	for (int i = 2; i < N; i++)
	{
		if (isprime[i])
			prime.push_back(i);
		for (int &it : prime)
		{
			if (1ll * i * it >= N)
				break;
			isprime[i * it] = 0;
			if (i % it == 0)
				break;
		}
	}
}

欧拉函数

性质 ： n的所有因数的欧拉函数之和等于n本身

ll phi(ll x)//容斥原理 O(sqrt(n))
{
    if(x == 1)
        return 1;
    ll ans = x;
    for (ll i = 2; i * i <= x; i++) 
    {
        if (x % i == 0) 
        {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) 
        ans = ans / x * (x - 1);
    return ans;
}

ll phi[N], prime[N];
ll tot;//tot计数，表示prime[N]中有多少质数 
void Euler()
{
    phi[1] = 1;
    for (ll i = 2; i < N; i++) 
    {
        if (!phi[i])
        {
            phi[i] = i - 1;
            prime[tot++] = i;

        }
        for (ll j = 0; j < tot && 1ll * i * prime[j] < N; j++)
        {
            if (i % prime[j]) 
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            else 
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}

矩阵快速幂

const int K = 2;
struct Matrix {
	ll a[K][K];
	Matrix() {}
	void clear() { memset(a, 0, sizeof a); }//变成0矩阵
	void init()//初始化为单位阵
	{
		clear();
		for (int i = 0; i < K; i++)
			a[i][i] = 1;
	}
	Matrix operator * (const Matrix& x) const
	{
		Matrix res;
		res.clear();
		for (int i = 0; i < K; i++)
			for (int j = 0; j < K; j++)
				for (int k = 0; k < K; k++)
					(res.a[i][j] += a[i][k] * x.a[k][j] % mod) %= mod;
		return res;
	}
	Matrix operator + (const Matrix& x) const
	{
		Matrix res;
		res.clear();
		for (int i = 0; i < K; i++)
			for (int j = 0; j < K; j++)
				res.a[i][j] = (a[i][j] + x.a[i][j]) % mod;
		return res;
	}
};

Matrix qpow(Matrix base, int pow)
{
	Matrix ans;
	ans.init();
	while (pow)
	{
		if (pow & 1)
			ans = ans * base;
		pow /= 2;
		base = base * base;
	}
	return ans;
}

void solve()
{
	Matrix x;
	int p[2][2] = { 1, 1, 1, 0 };
	memcpy(x.a, p, sizeof p);
	while (cin >> n, n != -1)
	{
		Matrix ans = qpow(x, n);
		cout << ans.a[0][1] << '\n';
	}
}

高斯消元

整数类型解

int a[maxn][maxn];
int ans[maxn];

int GCD ( int a, int b ) {
	if ( ! b )
		return a;
	return GCD ( b, a % b );
}
int LCM ( int a, int b ) {
	return a / GCD ( a, b ) * b;
}
int Fabs ( int x ) {
	if ( x < 0 )
		return -x;
	return x;
}

int Gauss ( int equ, int var ) { // 方程数、增广矩阵宽度， 传进来的是下标从1，1开始的增广矩阵
	for ( int i = 0;i <= var;i ++ ) {
		ans[i] = 0;
		Free[i] = 1;
	}
	int row, col, MaxRow;
	col = 1;
	for ( row = 1;row <= equ && col < var;row ++, col ++ ) {
		MaxRow = row;
		for ( int i = row + 1;i <= equ;i ++ )
			if ( Fabs ( a[i][col] ) > Fabs ( a[MaxRow][col] ) )
				MaxRow = i;
		if ( MaxRow != row ) {
			for ( int i = row;i <= var;i ++ )
				swap ( a[row][i], a[MaxRow][i] );
		}
		if ( ! a[row][col] ) {
			row --;
			continue;
		}
		for ( int i = row + 1;i <= equ;i ++ ) {
			if ( a[i][col] ) {
				int lcm = LCM ( Fabs ( a[i][col] ), Fabs ( a[row][col] ) );
				int T1 = lcm / Fabs ( a[i][col] );
				int T2 = lcm / Fabs ( a[row][col] );
				if ( a[i][col] * a[row][col] < 0 )
					T2 = -T2;
				for ( int j = col;j <= var;j ++ )
					a[i][j] = a[i][j] * T1 - a[row][j] * T2;
			}
		}
	}
	for ( int i = row;i <= equ;i ++ )
		if ( a[i][col] )
			return -1;
	int temp;
	if ( row < var ) {
		return var - row;
	}
	for ( int i = var - 1;i > 0;i -- ) {
		temp = a[i][var];
		for ( int j = i + 1;j < var;j ++ )
			if ( a[i][j] )
				temp -= a[i][j] * ans[j];
		ans[i] = temp / a[i][i];
	}
	return 0;
}

浮点数

double a[222][222];//下标从 0，0 开始
double ans[222],Free[222];//Free存放自由元
int Gauss ( int equ, int var ) {//方程数量，增广矩阵宽度-1(未知数个数)
	for ( int i = 0;i <= var;i ++ ) {
		ans[i] = 0;
		Free[i] = 1;
	}
	int row, col, MaxRow;
	col = 0;
	for ( row = 0;row < equ && col < var;row ++, col ++ ) {
		MaxRow = row;
		for ( int i = row + 1;i < equ;i ++ ) 
			if ( fabs ( a[i][col] ) > fabs ( a[MaxRow][col] ) )
				MaxRow = i;
		if ( MaxRow != row ) {
			for ( int i = row;i <= var;i ++ )
				swap ( a[row][i], a[MaxRow][i] );
		}
		if ( fabs ( a[row][col] ) < eps ) {//如果等于0
			row --;
			continue;
		}
		for ( int i = row + 1;i < equ;i ++ ) {
			if ( fabs ( a[i][col] ) > eps ) {
				double temp = a[i][col] / a[row][col];
				for ( int j = col;j <= var;j ++ )
					a[i][j] -= a[row][j] * temp;
				a[i][col] = 0;
			}
		}
	}
	for ( int i = row;i < equ;i ++ )
		if ( fabs ( a[i][col] ) > eps )
			return -1;
	double temp;
	if ( row < var ) {
		for ( int i = row - 1;i >= 0;i -- ) {
			int free_num = 0, idx;
			for ( int j = 0;j < var;j ++ )	
				if ( a[i][j] && Free[j] ) {
					free_num ++;
					idx = j;
				}
			if ( free_num > 1 )
				continue;
			temp = a[i][var];
			for ( int j = 0;j < var;j ++ ) {
				if ( a[i][j] && j != idx )
					temp -= a[i][j] * ans[j];
			}
			ans[idx] = temp / a[i][idx];//解出非自由元
			Free[idx] = 0;
		}
		return var - row;//自由元的数量，Free[i] 为 1 则为自由元
	}
	for ( int i = var - 1;i >= 0;i -- ) {
		temp = a[i][var];
		for ( int j = i + 1;j < var;j ++ )
			if ( a[i][j] )
				temp -= a[i][j] * ans[j];
		ans[i] = temp / a[i][i];
	}
	return 0;
}

模线性方程组（取模）

int a[N][N], ans[N];
int Gauss(int equ, int var) // 下标从 0,0 开始，equ 方程个数，var未知数个数
{
    for(int i = 0; i <= var; i++) ans[i] = 0; 
    int row, col = 0;
    for (row = 0; row < equ && col < var; row++, col++)
    {
        int MaxRow = row;
        for (int i = row + 1; i < equ; i++)
        {
            if (Abs(a[i][col]) > Abs(a[MaxRow][col]))
                MaxRow = i;
        }
        if (row != MaxRow)
        {
            for (int i = row; i <= var; i++)
                swap(a[row][i], a[MaxRow][i]);
        }
        if (!a[row][col])
        {
            row--;
            continue;
        }
        for (int i = row + 1; i < equ; i++)
        {
            if (a[i][col])
            {
                int T = a[i][col] * qpow(a[row][col], mod - 2) % mod;
                for (int j = col; j <= var; j++)
                    a[i][j] = (a[i][j] - a[row][j] * T % mod + mod) % mod;
            }
        }
    }

    for (int i = row; i < equ; i++)//无解
    {
        if (a[i][col])
            return -1;
    }
    if (row < var) return var - row;//多解
    for (int i = var - 1; i >= 0; i--)//x为答案
    {
        int temp = a[i][var];
        for (int j = i + 1; j < var; j++)
        {
            if (a[i][j])
            {
                temp -= a[i][j] * ans[j];
                temp = (temp % mod + mod) % mod;
            }
        }
        ans[i] = temp * qpow(a[i][i], mod - 2) % mod;
    }
    return 0;
}

异或

bitset<222> a[222];
int ans[222], Free[222], cnt;
int Gauss(int equ,int var){//下标从 0,0 开始，方程数量，增广矩阵宽度-1(未知数个数)
	int row, col, MaxRow;
	col = 0;
	for(row = 0; row < equ && col < var; row++, col++)
    {
		MaxRow = row;
		for(int i = row + 1; i < equ; i++) 
			if(abs(a[i][col]) > abs(a[MaxRow][col]))
				MaxRow=i;
		if(MaxRow != row) swap(a[row], a[MaxRow]);
		if(a[row][col] == 0)
        {
			row--;
			Free[++cnt]=col;
			continue;
		}
		for(int i = row + 1; i < equ; i++) if(a[i][col]) a[i] ^= a[row];
	}
	for(int i = row; i < equ; i++) if(a[i][col]) return -1;
	if(row<var) return var-row;
	for(int i = var - 1; i >= 0; i--)
    {
		ans[i] = a[i][var];
		for(int j = i + 1; j < var; j++) 
            if(a[i][j]) ans[i] ^= (a[i][j] && ans[j]);
	}
	return 0;
}

行列式求值

int a[N][N];
int calDet(int n, int mod)// a 数组下标从 1,1 开始，方阵
{
	int i, j, k, r = 1, fh = 0, l;
	for(i = 1; i <= n; i++)
	{
		k = i;
		for(j = i; j <= n; j++) if(a[j][i]) {k = j; break;}
		if(a[k][i] == 0) return 0;
		for(++j; j <= n; j++) if(a[j][i] && a[j][i] < a[k][i]) k = j;
		if(i != k) {swap(a[k], a[i]); fh ^= 1;}
		for(j = i + 1; j <= n; j++)
		{
			if(a[j][i] > a[i][i]) {swap(a[j], a[i]); fh ^= 1;}
			while(a[j][i])
			{
				l = a[i][i] / a[j][i];
				for(k = i; k <= n; k++) a[i][k] = (a[i][k] + (ll)(mod - l) * a[j][k]) % mod;
				swap(a[j], a[i]); fh ^= 1;
			}
		}
		r = (ll)r * a[i][i] % mod;
	}
	if(fh) return (mod - r) % mod;
	return r;
}

矩阵求逆

取模

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int mod=1e9+7;
int a[N][N<<1];//开宽度开两倍, 开始要将[1, n]初始化为求逆矩阵，[n + 1, 2 * n] 初始化为单位阵, 最后[n + 1, 2 * n]是逆矩阵
int n;
int ppow(int a,int b,int mod){
    int ans=1%mod;a%=mod;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int Gauss_rev(int n){
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){//找第i列非零的行换上来
            if(a[j][i]){
                swap(a[i],a[j]);
                break;
            }
        }
        if(!a[i][i])return 0;//无解
        int kk=ppow(a[i][i],mod-2,mod);//逆元
        for(int j=i;j<=n*2;j++){//当前行每一列都除以a[i][i]
            a[i][j]=1ll*a[i][j]*kk%mod;
        }
        for(int j=1;j<=n;j++){//其他行
            if(j!=i){
                kk=a[j][i];
                for(int k=i;k<=n*2;k++){
                    a[j][k]=(a[j][k]-1ll*kk*a[i][k]%mod+mod)%mod;
                }
            }
        }
    }
    return 1;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
        a[i][i+n]=1;
    }
    if(!Gauss_rev(n)){
        puts("No Solution");
    }else{
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                printf("%d ",a[i][j+n]);
            }
            puts("");
        }
    }
    return 0;
}

异或

bitset<N * 2> a[N];//开宽度开两倍, 开始要将[1, n]初始化为求逆矩阵，[n + 1, 2 * n] 初始化为单位阵, 最后[n + 1, 2 * n]是逆矩阵 
int Gauss_inv(int n) 
{
	for (int c = 1; c <= n; c++)
    {
		int t = c;
		for (int i = c; i <= n; i++) 
        {
			if (a[i][c]) 
            {
				t = i;
				break;
			}
		}
		if (a[t][c] == 0) return 0;//不存在逆矩阵
		swap(a[t], a[c]);
		for (int i = 1; i <= n; i++) if (a[i][c] && i != c) a[i] ^= a[c];
	}
	return 1;
}

线性基

void add(ll x)
{
    for(int i=60;i>=0;i--)
    {
        if(x&(1ll<<i))//注意，如果i大于31，前面的1的后面一定要加ll
        {
            if(d[i])
                x^=d[i];
            else
            {
                d[i]=x;
                break;//插入成功就退出
                //没有break就说明插入不成功，意味着 x 可以有当前的线性基异或得到
            }
        }
    }
}//最后d数组就是线性基

如何求最大值
完整的说，是如何求在一个序列中，取若干个数，使得它们的异或和最大。

首先构造出这个序列的线性基，然后从线性基的最高位开始，假如当前的答案异或线性基的这个元素可以变得更大，那么就异或它，答案的初值为 0

ll ans()
{
    ll anss = 0;
    for(int i = 60; i >= 0; i--)//记得从线性基的最高位开始
    if((anss ^ d[i]) > anss)
        anss ^= d[i];
    return anss;
 }   

如何求最小值
注意，这里指的是用线性基内的元素能异或出的最小值。

显然就是最小的 d [ i ]了，因为最小的 d [ i ]无论异或谁都会变大。

如果是求整个序列能异或出的最小值而不是这个序列的线性基能异或出的最小值的话，要另外看一看有没有元素不能插入线性基，如果有，那么最小值就是 0，否则依然是最小的 d [ i ]。

从一个序列中取任意个元素进行异或，求能异或出的所有数字中第 $k$ 小的那个。

void work()//处理线性基
{
	for(int i=1;i<=60;i++)
	for(int j=1;j<=i;j++)
	if(d[i]&(1ll<<(j-1)))d[i]^=d[j-1];
}
ll k_th(ll k)
{
	if(k==1&&tot<n)return 0;//特判一下，假如k=1，并且原来的序列可以异或出0，就要返回0，tot表示线性基中的元素个数，n表示序列长度
	if(tot<n)k--;//类似上面，去掉0的情况，因为线性基中只能异或出不为0的解
	work();
	ll ans=0;
	for(int i=0;i<=60;i++)
	if(d[i]!=0)
	{
		if(k%2==1)ans^=d[i];
		k/=2;
	}
    return ans;
}

康托展开

曼哈顿距离

$dis(a, b) = |i_a - i_b| + |j_a - j_b|$

​ $ = max(i_a - i_b, i_b - i_a) + max(j_a - j_b, j_b - j_a)$//做笛卡尔积

​ $ = max(|(i_a + j_a) - (i_b + j_b)|, |(i_a - j_a) - (i_b - j_b)|)$

令 $z_a = i_a + j_a, w_a = i_a - j_a, z_b = i_b + j_b, w_b = i_b - j_b$;

$dis(a, b) = |z_a - z_b| + |w_a - w_b|$

平面上若求一个点$(x, y)$到一个点集的最大曼哈顿距离

则只需要维护 $z$的最大值最小值，$w$的最大值最小值

最终答案为 $max(z_{max} - z_x, z_x - z_{min}, w_{max} - w_x, w_x - w_{min})$

例题 ： 求一个位置，使得其到所有黑点最大曼哈顿距离最小，我们枚举位置，之后最大距离取min即可。

//https://codeforces.com/contest/1689/problem/D
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const ll mod = 1e9 + 7;
const ll N = 1e3 + 5;

ll n, m;
char g[1005][1005];

void solve()
{
	cin >> n >> m;
	cin.ignore();
	for (ll i = 1; i <= n; i++)
		for (ll j = 1; j <= m; j++)
			cin >> g[i][j];
	ll zmi = inf, zmx = -inf, wmi = inf, wmx = -inf;
	for (ll i = 1; i <= n; i++)
	{
		for (ll j = 1; j <= m; j++)
		{
			if(g[i][j] == 'B')
			{
				zmi = min(zmi, i + j);
				zmx = max(zmx, i + j);
				wmi = min(wmi, i - j);
				wmx = max(wmx, i - j);
			}
		}
	}
	ll dis = inf;
	pair<ll, ll> ans;
	for (ll i = 1; i <= n; i++)
	{
		for (ll j = 1; j <= m; j++)
		{
			ll zx = i + j;
			ll wx = i - j;
			ll diss = max({ zmx - zx, zx - zmi, wmx - wx, wx - wmi });
			if (diss < dis)
			{
				dis = diss;
				ans = { i, j };
			}
		}
	}
	cout << ans.first << ' ' << ans.second << '\n';
}

signed main()
{
	IOS;
	ll t = 1;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

曼哈顿距离和切比雪夫距离的转化

曼哈顿距离转切比雪夫距离 $(x,y)->(x+y, x-y)$

切比雪夫距离转曼哈顿距离 $(x, y) -> (\frac{x+y}{2}, \frac{x-y}{2})$

质因数分解求给定正整数的因数个数

正整数因数个数的快速求法
以72为例，将72进行质因数分解，72 = $22233$ = $2^3 * 3^2$
将底数2的幂次和底数3的幂次分别加1再相乘
得到72的因数个数 = (3+1) * (2+1) = 12
对特殊的数如 1，质数均成立

min_25筛

​ 求大区间素数个数

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int S = 1e6; // S = sqrt(N);N是范围
int isprime[S];
vector<int> prime;
ll v[S], f[S];
double inv[S];
void sieve() {
    fill(isprime + 2, isprime + S, 1);
    for (int i = 2; i < S; ++i)
    {
        if (isprime[i]) prime.push_back(i);
        for (auto &p : prime) 
        {
            if (i * p >= S) break;
            isprime[i * p] = 0;
            if (i % p == 0) break;
        }
    }
}
ll get(long long n) { // 返回 [1,n] 的素数个数
    if (n <= 1) return 0;

    int lim = sqrt(n);
    int cnt = 0;
    for (ll i = 1; i <= n; i = n / (n / i) + 1)
        v[cnt++] = n / i;
    auto getid = [&](long long x) {
        return x <= lim ? cnt - x : n / x - 1;
    };
    for (int i = 0; i < cnt; ++i)
        f[i] = v[i] - 1;
    for (int i = 0; prime[i] <= lim; ++i)
        for (int j = 0; j < cnt && 1ll * prime[i] * prime[i] <= v[j]; ++j)
            f[j] -= f[getid(v[j] * inv[prime[i]] + 1e-9)] - i;
    return f[0];
}
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    for (int i = 1; i < S; ++i)
        inv[i] = 1.0 / i;
    sieve();
    
    ll n;
    cin >> n;
    cout << get(n) << '\n';
    return 0;
}

Miller_Rabin

判断大数是否为素数

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline ll mul(ll x, ll y, ll mod) {
    return (__int128)x * y % mod;
}
inline ll qpow(ll x, ll y, ll mod) {
    ll res = 1;
    for (; y; y >>= 1, x = mul(x, x, mod))
        if (y & 1)
            res = mul(res, x, mod);
    return res;
}
const int pr[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(ll x)//O(7log)
{
    if (x < 3 || x % 2 == 0) return x == 2;
    int r = 0;
    ll k = x - 1;
    while(k % 2 == 0) k /= 2, ++r;
    
    for (int T = 0; T <= 6; T++) 
    {
        ll p = pr[T];
        if (p % x == 0) continue;
        ll v = qpow(p, k, x);
        if (v == 1) continue;
        int j;
        for (j = 1; j <= r; j++, v = mul(v, v, x)) if (v == x - 1) break;
        if (j > r) return 0;
    }
    return 1;
}

void solve()
{
    ll x;
    while(cin >> x) cout << (isprime(x) ? "Y" : "N") << '\n';
}

Pollard rho

可以分解出大数的质因子(改 get)，用 $Pollard rho$ 找出一个因子 $x$，然后接着对 $x$ 和 $\frac{n}{x}$ 用 $Pollard rho$ 来分解

以下代码为找出大数的最大质因子

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll max_factor, n;
ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

inline ll mul(ll x, ll y, ll mod) {
    return (__int128)x * y % mod;
}
inline ll qpow(ll x, ll y, ll mod) {
    ll res = 1;
    for (; y; y >>= 1, x = mul(x, x, mod))
        if (y & 1)
            res = mul(res, x, mod);
    return res;
}
const int pr[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
bool Miller_Rabin(ll x)//判断素数 O(7log)
{
    if (x < 3 || x % 2 == 0) return x == 2;
    int r = 0;
    ll k = x - 1;
    while(k % 2 == 0) k /= 2, ++r;
    
    for (int T = 0; T <= 6; T++) 
    {
        ll p = pr[T];
        if (p % x == 0) continue;
        ll v = qpow(p, k, x);
        if (v == 1) continue;
        int j;
        for (j = 1; j <= r; j++, v = mul(v, v, x)) if (v == x - 1) break;
        if (j > r) return 0;
    }
    return 1;
}

ll Pollard_Rho(ll x) //返回 x 的一个因子， O(n^(1/4))
{
    ll s = 0, t = 0;
    ll c = rand() % (x - 1) + 1;
    ll val = 1;
    for (int goal = 1; ; goal *= 2, s = t, val = 1)// 倍增优化
    { 
        for (int step = 1; step <= goal; ++step)
        {
            t = ((__int128)t * t + c) % x;
            val = mul(val, abs(t - s), x);
            if (step % 127 == 0)
            {
                ll d = gcd(val, x);
                if (d > 1) return d;
            }
        }
        ll d = gcd(val, x);
        if (d > 1) return d;
    }
}

void get(ll x)
{
    if (x <= max_factor || x < 2) return;
    if (Miller_Rabin(x))
    {                                    // 如果x为质数
        max_factor = max(max_factor, x); // 更新答案
        return;
    }
    ll p = x;
    while (p >= x) p = Pollard_Rho(x); // 使用该算法
    while (x % p == 0) x /= p;
    get(x), get(p); // 继续向下分解x和p
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        srand((unsigned)time(NULL));
        max_factor = 0;
        scanf("%lld", &n);
        get(n);
        if (max_factor == n) // 最大的质因数即自己
            printf("Prime\n");
        else
            printf("%lld\n", max_factor);
    }
    return 0;
}