题解

3 条题解

  • 14
    @ 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
    @ 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
    @ 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

  • 1

信息

ID
2025
难度
7
分类
(无)
标签
(无)
递交数
187
已通过
30
通过率
16%
被复制
5
上传者