题解 - Vijos

14

dashuai LV 8 @ 2017-10-08 15:29:51

官方题解

注意到 ϕ(n)/(n−1) 展开后等于 n/(n−1) 乘上若干个 (p-1)/p 这里 p 是 n 的素因子，且 p 不会重复出现。那么换句话说除了前面 n/(n−1) 后面部分的结果与一个素因子在 n 中出现多少次没有关系。进而想到如果不考虑 n/(n−1) 只看后面部分的乘积，最优方案一定是最小若干个素数的乘积。也就是 2,2×3,2×3×5,2×3×5×7,2×3×5×7×11等。而多了 n/(n−1)，答案应该是上述形式的倍数，且不会倍率非常大（因为 n 比较大的时候 n/(n−1) 几乎等于 1）。这就得到了最终的算法。

个人代码：

#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

*/

2

fjzzq2002 LV 8 @ 2017-10-08 11:07:27

python大法好，代码略丑

AB=raw_input().split(' ')
A,B=int(AB[0]),int(AB[1])
np=[1]*2+[0]*100000
ps=[]
def phi(a,s):
    ans=a
    for r in range(0,s+1):
        p=ps[r]
        if a%p==0:
            ans=ans/p*(p-1)
    return ans
for i in range(2,10000):
    if np[i]:
        continue
    ps.append(i)
    j=i+i
    while j<=10000:
        np[j]=1
        j=j+i
x=1
lx=1
p=1
lp=1
r=0
while p*B>=A*(x-1):
    s=ps[r]
    lx,lp=x,p
    p=p*(s-1)
    x=x*s
    r=r+1
r=r-1
x=lx
L,R=1,ps[r]
while L<R:
    M=L+((R-L)>>1)
    xx=x*M
    pp=phi(xx,r+1)
    if pp*B<A*(xx-1):
        R=M
    else:
        L=M+1
print L*x

0

real_hdsy_gyz LV 10 @ 2022-02-27 15:54:30

首页
题库
训练
讨论
比赛
作业
排名
real_hdsy_gyz
/ Vijos / 题库 / 欧拉函数 /
题解
2 条题解
0
real_hdsy_gyz LV 0
发表您的题解
14

dashuai LV 8 @ 4 年前
官方题解

注意到 ϕ(n)/(n−1) 展开后等于 n/(n−1) 乘上若干个 (p-1)/p 这里 p 是 n 的素因子，且 p 不会重复出现。那么换句话说除了前面 n/(n−1) 后面部分的结果与一个素因子在 n 中出现多少次没有关系。进而想到如果不考虑 n/(n−1) 只看后面部分的乘积，最优方案一定是最小若干个素数的乘积。也就是 2,2×3,2×3×5,2×3×5×7,2×3×5×7×11等。而多了 n/(n−1)，答案应该是上述形式的倍数，且不会倍率非常大（因为 n 比较大的时候 n/(n−1) 几乎等于 1）。这就得到了最终的算法。

个人代码：

#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

*/
Copy
2

fjzzq2002 LV 8 @ 4 年前
python大法好，代码略丑

AB=raw_input().split(' ')
A,B=int(AB[0]),int(AB[1])
np=[1]*2+[0]*100000
ps=[]
def phi(a,s):
ans=a
for r in range(0,s+1):
p=ps[r]
if a%p==0:
ans=ans/p*(p-1)
return ans
for i in range(2,10000):
if np[i]:
continue
ps.append(i)
j=i+i
while j<=10000:
np[j]=1
j=j+i
x=1
lx=1
p=1
lp=1
r=0
while p*B>=A*(x-1):
s=ps[r]
lx,lp=x,p
p=p*(s-1)
x=x*s
r=r+1
r=r-1
x=lx
L,R=1,ps[r]
while L<R:
M=L+((R-L)>>1)
xx=x*M
pp=phi(xx,r+1)
if pp*B<A*(xx-1):
R=M
else:
L=M+1
print L*x
Copy
1
欧拉函数
查看题目
递交
讨论
题解
信息
ID2025递交 Accepted难度8分类(无)标签(无)递交数182我的递交数1已通过27通过率15%被复制4上传者 doc
状态
评测队列
服务状态
开发
开源
API
支持
帮助
QQ 群
关于联系我们隐私服务条款版权申诉 Language
© 2005 - 2021 Vijos.orgbuild20210206-1-gb0e1685沪ICP备14040537号-1

题解

3 条题解

欧拉函数

信息

状态

开发

支持

还没有账户？

登录