跳到主要内容

筛质数分解质因数和快速幂

AcWing 197. 阶乘分解​

题目​

给定整数 N，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 pip_i 和 cic_i 即可。

思路​

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    int n;
    cin >> n;
    init(n);
    for (int i = 0; i < cnt; i++) {
        int p = primes[i];
        int s = 0;
        for(int j=n;j;j/=p) s+=j/p;
        cout<<p<<" "<<s<<endl;
    }
    return 0;
}

AcWing 1289. 序列的第k个数​

题目​

https://www.acwing.com/problem/content/1291/ BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。 现在给你 整数 序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。 如果第 k 项的值太大，对其取模 200907。

思路​

等差数列：a,b,c满足：2*b=a+c,第k项为ak=a1+(k−1)(b−a)a_k=a_1+(k-1)(b-a) d=b-a 等比数列：a,b,c满足：b*b=a*c,第k项为ak=a⋅(b/a)k−1a_k=a·(b/a)^{k-1}

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int mod=200907;

int a,b,c,k;
LL qmi(int a,int k)
{
    LL res=1;
    while (k)
    {
        if (k&1) res=(LL)res*a%mod;
        a=(LL) a*a%mod;
        k>>=1;
    }
    return res;
}

int main() {
    int t;
    cin>>t;
    while (t--)
    {
        cin>>a>>b>>c>>k;
        if (a+c==2*b) cout<<(a+(b-a)*(LL)(k-1))%mod<<endl;
        
        else cout << (LL)a * qmi(b / a, k - 1) % mod << endl;
    }

    return 0;
}

AcWing 1290. 越狱​

题目​

https://www.acwing.com/activity/content/problem/content/1735/ 监狱有连续编号为 1 到 n 的 n 个房间，每个房间关押一个犯人。 有 m 种宗教，每个犯人可能信仰其中一种。 如果相邻房间的犯人信仰的宗教相同，就可能发生越狱。 求有多少种状态可能发生越狱。

思路​

利用容斥原理： 总可能个数为mnm^n 不发生越狱的情况为第一个可以选m个宗教，第2-n个可以选m-1个，总个数为:m∗(m−1)n−1m*(m-1)^{n-1} 可能发生越狱的情况为：mn−m∗(m−1)n−1m^n-m*(m-1)^{n-1}

代码​

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int mod=1e5+3;
LL n,m;

LL qmi(int a,LL k){
    LL res=1;
    while (k){
        if (k&1) res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        k>>=1;
    }
    return res;
}

int main() {
    cin>>m>>n;
    cout<<((qmi(m,n)-(LL)m*(qmi(m-1,n-1)))%mod+mod)%mod<<endl;

    return 0;
}

0%