注意:函数传数组传的是指针，并非copy一份，所以必须用一个tmp数组

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;
LL g[3][3];int n,m;

void mul(LL ans[3],LL vec[3],LL mat[3][3])
{
    LL tmp[3] = {0};
    for(int i = 0;i < 3;i ++ )
    {
        for(int j = 0;j < 3;j ++ )
            tmp[i] = (tmp[i] + vec[j] * mat[j][i]) % m; 
    }
    memcpy(ans,tmp,24);
}

void mul(LL ans[3][3],LL mat1[3][3],LL mat2[3][3])
{
    LL tmp[3][3] = {0};
    for(int i = 0;i < 3;i ++ )
        for(int j = 0;j < 3;j ++ )
            for(int k = 0;k < 3;k ++ )
                tmp[i][j] = (tmp[i][j] + mat1[i][k] * mat2[k][j]) % m;
    memcpy(ans,tmp,72);
}

void qmi(LL ans[3],LL mat[3][3],LL b)
{
    while(b)
    {
        if(b & 1) mul(ans,ans,mat);
        mul(mat,mat,mat);
        b >>= 1;
    }
}

int main()
{
    fastio();
    cin >> n >> m;
    LL ans[3] = {1,1,1};
    LL g[3][3] = {
        {0,1,0},
        {1,1,1},
        {0,0,1},
    };
    qmi(ans,g,n - 1);
    cout << ans[2] << endl;
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;
inline LL gcd(LL a,LL b){return b ? gcd(b,a % b) : a;}

LL phi(LL n)
{
    LL res = n;
    for(int i = 2;i <= n / i && n;i ++ )
        if(n % i == 0)
        {
            res = res / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    if(n > 1) res = res / n * (n - 1);
    return res;
}
bool check(LL x,LL C)
{
    auto qmul = [&](LL a,LL b)// 龟速加
    {
        LL res = 0;
        while(b)
        {
            if(b & 1) res = (res + a) % C;
            a = (a + a) % C;
            b >>= 1;
        }
        return res;
    };
    auto qmi = [&](LL a,LL b)// 快速幂
    {
        LL res = 1;
        while(b)
        {
            if(b & 1) res = qmul(res,a);
            a = qmul(a,a);
            b >>= 1;
        }
        return res;
    };
    return qmi(10,x) % C == 1;
}
int main()
{
    fastio();
    int T = 0;LL L;
    while(cin >> L,L)
    {
        LL C = 9 * L / gcd(L,8),D = phi(C);
        LL res = D;
        if(gcd(10,C) != 1) res = 0;
        else
        {
            for(LL i = 1;i <= D / i;i ++ )
            {
                if(D % i == 0)
                {
                    if(check(i,C)) res = min(res,i);
                    if(check(D / i,C)) res = min(res,D / i);
                }
            }
        }
        printf("Case %d: %lld\n",++ T ,res);
    }
    return 0;
}

1.中国剩余定理

$$x\equiv a_i(\mathsf{mod}\;m_i)$$

$condition:\displaystyle{\forall i \ne j,(m_i,m_j) = 1}$

$assume:\displaystyle{M_i = \frac{m_1\times m_2\times\cdots m_n}{m_i}},M_it_i\equiv1(\mathsf{mod}\;m_i)$

$ans:x = \displaystyle{\sum_{i = 1}^n a_iM_it_i}$

Code

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;
constexpr int N = 12;
typedef long long LL;
int b[N],a[N];

LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b) return (x = 1,y = 0,a);
    LL d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}

int main()
{
    fastio();
    int n;cin >> n;
    LL mul = 1;
    for(int i = 0;i < n;i ++ ) 
        cin >> a[i] >> b[i],mul *= a[i];
    LL res = 0,t,m,k;
    for(int i = 0;i < n;i ++ )
    {
        m = mul / a[i];
        exgcd(m,a[i],t,k);
        res = res + b[i] * m * t;
    }
    cout << (res % mul + mul) % mul << endl;
    return 0;
}

2.扩展欧几里得算法推导中国剩余定理

Code

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b) return (x = 1,y = 0,a);
    LL d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main()
{
    fastio();
    int n;cin >> n;
    LL a1,b1,a2,b2,k1,k2;
    cin >> b1 >> a1;
    while(-- n )
    {
        cin >> b2 >> a2;
        exgcd(b1,b2,k1,k2);
        k1 = k1 * (a2 - a1);
        k1 = (k1 % b2 + b2) % b2;
        a1 = a1 + k1 * b1;
        b1 = b1 * b2;
    }
    cout << (a1 % b1 + b1) % b1 << endl;
    return 0;
}

Q:给定一个正整数 $L$，请问至少多少个8连在一起组成的正整数是 $L$的倍数。

• 该题限制范围故意下毒: $L \times L $ 达到了 $4e18$ 的级别，而题目中实际上用到的数据要大于 $L$,存在爆 $long\;long$的风险
• 使用龟速乘解决

Sol.1:

q1:$\mathsf{8连在一起的正整数}$:

设$a_n$表示目标序列，且$a_1 = 8$,可以看出:
$$a_n = 10a_{n - 1} + 8$$
使用高中所学的不动点法，可以整理上式为:
$$a_n + \frac{8}{9} = 10(a_{n - 1}+\frac{8}{9})$$
所以通项公式为:
$$a_n = \frac{8}{9}(10^n - 1)$$

Sol.1 -> Solv.2

所以原问题为:
$$\frac{8}{9}(10^x - 1) \equiv 0(\mathsf{mod}\;L)\Leftrightarrow \frac{8}{gcd(L,8)}(10^x - 1)\equiv 0(\mathsf{mod}\;9\frac{L}{gcd(L,8)})$$

令
$$C = 9\frac{L}{gcd(L,8)}$$

Sol.2

q2:$\mathsf{求最小的x,使得}10^x \equiv 1(\mathsf{mod}\;C)$:

更一般地，我们可以求出最小的 $x$,在 $gcd(a,x) = 1$条件下,使得:
$$a^x\equiv 1(\mathsf{mod}\;C)$$

证:

由欧拉定理知,当 $x_0=\varphi(C)$ 时满足上式

结论:最小的满足要求的 $x$ 是 $\varphi(C)$ 的约数

反证法:设最小的满足要求的 $x为x_1(x_1\leq \varphi(C))$ 不是 $\varphi(C)$ 的约数，则 $\varphi(C)$ 可由带余除法写出:
$$\varphi(C) = kx_1 + d(0<d<x_1)$$

代入，有:
\begin{cases}
a^\varphi(C)\equiv 1(\mathsf{mod}\;C)\\
\\
a^{x_1}\equiv 1(\mathsf{mod}\;C)\\
\\
a^{\varphi(C)} = a^{kx_1 + d} = a^{kx_1} \times a^d\\
\end{cases}

所以 $a^d\equiv 1(\mathsf{mod}\;C)$ ,而 $d$ 满足 $(0<d<x_1)$ ,这与 $x_1$ 是最小的这一前提矛盾

code

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;
inline LL gcd(LL a,LL b){return b ? gcd(b,a % b) : a;}

LL phi(LL n)
{
    LL res = n;
    for(int i = 2;i <= n / i && n;i ++ )
        if(n % i == 0)
        {
            res = res / i * (i - 1);
            while(n % i == 0) n /= i;
        }
    if(n > 1) res = res / n * (n - 1);
    return res;
}
bool check(LL x,LL C)
{
    auto qmul = [&](LL a,LL b)// 龟速乘
    {
        LL res = 0;
        while(b)
        {
            if(b & 1) res = (res + a) % C;
            a = (a + a) % C;
            b >>= 1;
        }
        return res;
    };
    auto qmi = [&](LL a,LL b)// 快速幂
    {
        LL res = 1;
        while(b)
        {
            if(b & 1) res = qmul(res,a);
            a = qmul(a,a);
            b >>= 1;
        }
        return res;
    };
    return qmi(10,x) % C == 1;
}
int main()
{
    fastio();
    int T = 0;LL L;
    while(cin >> L,L)
    {
        LL C = 9 * L / gcd(L,8),D = phi(C);
        LL res = D;
        if(gcd(10,C) != 1) res = 0;
        else
        {
            for(LL i = 1;i <= D / i;i ++ )
            {
                if(D % i == 0)
                {
                    if(check(i,C)) res = min(res,i);
                    if(check(D / i,C)) res = min(res,D / i);
                }
            }
        }
        printf("Case %d: %lld\n",++ T ,res);
    }
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b) return(x = 1, y = 0,a);
    LL d = exgcd(b,a % b,y,x);
    y -= (a / b) * x;
    return d;
}
int main()
{
    fastio();
    LL x,y,m,n,L,t,k;
    cin >> x >> y >> m >> n >> L;
    LL d = exgcd(m - n,L,t,k);
    if((y - x) % d) cout << "Impossible" << endl;
    else
    {
        LL ans = t * (y - x) / d;
        LL mod = abs(L / d);
        cout << (ans % mod + mod) % mod << endl;
    }
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;

int exgcd(int a,int b,int& x,int& y)
{
    if(!b) return (x = 1,y = 0,a);
    int t = exgcd(b,a % b,y,x);
    y -= a / b * x;
    return t;
}

int main()
{
    fastio();
    // ax + bk = 1
    // x = x0 + t * b / 1;
    int a,b,x,k;cin >> a >> b;
    exgcd(a,b,x,k);
    cout << (x % b + LL(b)) % b << endl;
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define endl '\n'
using namespace std;
constexpr int N = 10000010;
typedef long long LL;
bool st[N];
int prime[N],cnt;
LL phi[N];
void euler(int n)
{
    for(int i = 2;i <= n;i ++ )
    {
        if(!st[i]) prime[cnt ++ ] = i,phi[i] = i - 1;
        for(int j = 0;prime[j] <= n / i;j ++ )
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) 
            {
                phi[prime[j] * i] = prime[j] * phi[i];
                break;
            }
            phi[prime[j] * i] = (prime[j] - 1) * phi[i];
        } 
    }
    for(int i = 1;i <= n;i ++ ) phi[i] += phi[i - 1];
}
void solve()
{
    int n;cin >> n;
    euler(n);LL res = 0;
    for(int i = 0;i < cnt;i ++ ) res += phi[n / prime[i]];
    cout << (res << 1) + cnt << endl; 
}
int main()
{
    fastio();
    int T = 1;
    while(T -- ) solve();
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define endl '\n'
using namespace std;
constexpr int N = 50010;
typedef long long LL;
bool st[N];
int prime[N],cnt;
int phi[N];
void euler(int n)
{
    phi[1] = 1;
    for(int i = 2;i <= n;i ++ )
    {
        if(!st[i]) prime[cnt ++ ] = i,phi[i] = i - 1;
        for(int j = 0;prime[j] <= n / i;j ++ )
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) 
            {
                phi[prime[j] * i] = prime[j] * phi[i];
                break;
            }
            phi[prime[j] * i] = (prime[j] - 1) * phi[i];
        } 
    }
}
void solve()
{
    int n;cin >> n;
    euler(n);
    int res = 0;
    for(int i = 1;i <= n;i ++ ) res += phi[i];
    cout << n << " " << (res << 1) + 1 << endl;
}
int main()
{
    fastio();
    int T;cin >> T;
    for(int i = 1;i <= T;i ++ )
    {
        cout << i << " ";
        solve();
    }
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define endl '\n'
using namespace std;
constexpr int N = 50010;
typedef long long LL;
typedef pair<int,int> PII;
inline int gcd(int a,int b) {return b ? gcd(b,a % b) : a;}
int a,b,c,d;
bool st[N];
vector<int> prime;
vector<int> divisor;
struct factor
{
    int p,s;
}fact[N];
int fcnt;
void init()
{
    int n = N - 1;
    for(int i = 2;i <= n;i ++ )
    {
        if(!st[i]) prime.push_back(i);
        for(int j = 0;prime[j] * i <= n;j ++ )
        {
            st[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
void work(int k)
{
    fcnt = 0;
    for(int i = 0;i < prime.size() && k;i ++ )
    {
        if(k % prime[i] == 0)
        {
            int s = 0;
            while(k % prime[i] == 0) k /= prime[i],s ++ ;
            fact[fcnt ++ ]  = {prime[i],s};
        }
    }
    if(k > 1) fact[fcnt ++ ] = {k,1};
}
void get_divisors(int u,int mul)
{
    if(u == fcnt) return void(divisor.push_back(mul));
    else
    {
        for(int i = 0;i <= fact[u].s;i ++ )
        {
            get_divisors(u + 1,mul);
            mul *= fact[u].p;
        }
    }
}
void solve()
{
    divisor.clear();
    cin >> a >> b >> c >> d;
    work(d),get_divisors(0,1);
    int res = 0;
    for(int i = 0;i < divisor.size();i ++ )
    {
        int x = divisor[i];
        if(gcd(a,x) == b && (LL)c * x / gcd(c,x) == d) res ++;
    }
    cout << res << endl;
}
int main()
{
    fastio();
    init();
    int T;cin >> T;
    while(T -- ) solve();
    return 0;
}

#include <bits/stdc++.h>

#define fastio() ios::sync_with_stdio(0),\
        cin.tie(0),cout.tie(0);
#define lowbit(x) (x & -x)
#define endl '\n'
using namespace std;

typedef long long LL;
int prime[] = {2,3,5,7,11,13,17,19,23};
int n,ans,num;
void dfs(int u,int last,int mul,int sum)
{
    if(sum > ans || (sum == ans && mul < num))
    {
        ans = sum;
        num = mul;
    }
    if(u == 9) return;
    for(int i = 1;i <= last;i ++ )
    {
        LL ne = 1LL * mul * prime[u];
        if(ne > n) break;
        mul = ne;
        dfs(u + 1,i,mul,sum * (i + 1));
    }
}
int main()
{
    fastio();
    cin >> n;
    dfs(0,30,1,1);
    cout << num << endl;
    return 0;
}