/ WSoi /

# 记录详情

# 状态 耗时 内存占用
#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