AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

默写(数论)

作者: 作者的头像   DKing2917 ,  2024-10-31 19:17:25 ,  所有人可见 ,  阅读 4


0


#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;

const int N = 5010;
int prime[N], cnt;
bool sta[N];
int a, b, sum[N];

void get_prime(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(sta[i] == false)
            prime[cnt ++] = i;
        for(int j = 0; prime[j] <= n/i; j ++)
        {
            sta[prime[j] * i] = true;
            if(i % prime[j] == 0)
                break;
        }
    }

}
int get(int n, int p)
{
    int res = 0;
    while(n)
    {
        res += n/p;
        n /= p;
    }
    return res;
}
vector<int> mul(vector<int> a, int b)
{
    vector<int> C;
    if(b == 0)
    {
        C.push_back(0);
        return C;
    }
    int t = 0;
    for(int i = 0; i < a.size(); i ++)
    {
        t += a[i] * b;
        C.push_back(t%10);
        t /= 10;
    }
    while(t)
    {
        C.push_back(t%10);
        t /= 10;
    }
    return C;
}
int main()
{
    scanf("%d %d", &a, &b);

    get_prime(a);

    //得到每个质数的幂次
    for(int i = 0; i < cnt; i ++)
    {
        sum[i] = get(a, prime[i]) - get(b, prime[i]) - get(a-b, prime[i]);
    }

    vector<int> C; C.push_back(1);
    for(int i = 0; i < cnt; i ++)
        for(int j = 0; j < sum[i]; j++)
            C = mul(C, prime[i]);

    for(int i = C.size()-1; i >=0 ; i --)
        printf("%d", C[i]);

    return 0;
}

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息