/ WSoi /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Wrong Answer 成績取消 0ms 0 Bytes

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;

const int N=60;
const int Mod=10000;

struct bignum{//高精模板,压万进制
    int len;
    int num[N];
    bignum (){len=1;memset(num,0,sizeof(num));}
    void out(){
        printf("%d",num[len]);
        for(int i=len-1;i;--i)printf("%04d",num[i]);
        putchar('\n');
    }
    bignum operator =(const char *s){
        {len=1;memset(num,0,sizeof(num));}
        len=strlen(s);
        for(int i=0;i<len;++i)
        num[(len-i-1)/4+1]=num[(len-i-1)/4+1]*10+s[i]-'0';
        len=len/4+1;
        while(num[len]==0&&len>1)--len;
        return *this;
    }
    bignum operator =(const int &k){
        char s[12];
        sprintf(s,"%d",k);
        *this=s;
        return *this;
    }
    bignum(const int &k){*this=k;}
    bignum operator +(const bignum &b){
        bignum c;
        c.len=max(len,b.len)+1;
        for(int i=1;i<=c.len;++i){
            c.num[i]+=num[i]+b.num[i];
            if(c.num[i]>=Mod){
                c.num[i]-=Mod;
                ++c.num[i+1];
            }
        }
        while(c.len>1&&c.num[c.len]==0)--c.len;
        return c;       
    }
    bignum operator *(const bignum &b){
        bignum c;
        c.len=len+b.len+1;
        for(int i=1;i<=len;++i)
        for(int j=1;j<=b.len;++j){
            c.num[i+j-1]+=num[i]*b.num[j];
            if(c.num[i+j-1]>=Mod){
                c.num[i+j]+=c.num[i+j-1]/Mod;
                c.num[i+j-1]%=Mod;
            }
        }
        while(c.len>1&&c.num[c.len]==0)--c.len;
        return c;
    }
    bignum operator /(const int &b){
        bignum c;
        c=*this;
        int k=0;
        for(int i=len;i;--i){
            c.num[i]+=k*Mod;
            k=c.num[i]%b;
            c.num[i]/=b;
        }
        while(c.len>1&&c.num[c.len]==0)--c.len;
        return c;
    }
    bool operator <(const bignum &b)const {
        if(len!=b.len)return len<b.len;
        for(int i=len;i;--i)
        if(num[i]!=b.num[i])return num[i]<b.num[i];
        return false;
    }
};

bignum n,phi;
int cnt;
int prime[Mod];

int A,B;

bool is_prime(int x){
    for(int i=2;i<=sqrt(x)+0.5;++i)
    if(x%i==0)return 0;
    return 1;
}
int main(){
    scanf("%d%d",&A,&B);
    for(int i=2;i<=600;++i)
    if(is_prime(i))prime[++cnt]=i;
    n=1;
    phi=1;
    for(int i=1;i<=93;++i){//前93个素数乘积超过200位
        n=n*prime[i];//n为前i个不同质数的乘积
        phi=phi*(prime[i]-1);
        for(int j=1;j<prime[i+1];++j){
            bignum tmp1,tmp2;
            tmp1=phi*B*j;
            tmp2=n*j;
            --tmp2.num[1];
            if(tmp1<tmp2*A){
                tmp2.num[1]++;
                tmp2.out();
                return 0;
            }
        }
    }
    return 0;
}
/*
1 3  30
1 4  210
1 5  30030
2 9  2310
3 11  60
1 9  1492182350939279320058875736615841068547583863326864530410

*/

信息

递交者
类型
递交
题目
P1020 欧拉函数
题目数据
下载
语言
C++
递交时间
2020-07-28 16:19:19
评测时间
2021-04-28 03:28:03
评测机
分数
0
总耗时
0ms
峰值内存
0 Bytes