P8814 [CSP-J 2022] 解密 題解

· · 题解

P8814 [CSP-J 2022] 解密 題解

题意

给定：

\left\{\begin{array}{l} n=p q \\ ed=(p-1) (q-1)+1 \end{array}\right.

已知 n,e,d，求 p,q。

解析 数学法

拆一下上面的式子，得：

\left\{\begin{array}{l} n = pq \\ n - ed + 2 = p + q \end{array}\right.

根据第一个式子，得到 q = \dfrac{n}{p}。

代入第二个式子：

p^{2}-(n-ed+2) p+n=0

因为 n,d,e 已知，a=1, b=(n - ed +2), c=n，算出判别式：

\Delta = b^2 - 4ac = (n - ed + 2) - 4n

代入算出 p 的公式：

p = \dfrac{n - ed + 2 ± \sqrt{\Delta} }{2}

直接计算即可。

代码 数论法

一定要细心。

#include<bits/stdc++.h>

#define int long long
#define fore(i,x,n) for(int i=x;i<=n;i++)

const int MAXX=10005;
const int mod=1;

inline int __read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

inline void __write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) __write(x/10);
    putchar(x%10+'0');
}

inline void __writesp(int x){
    __write(x);
    putchar(' ');
}
int n,d,e;

inline void input(){
    n=__read(); d=__read(); e=__read();
}

inline void work(){
    int b=(-n-e*d+2),c=n;
    int d=b*b-4*c;
    if(d<0){ puts("NO"); return; }
    if(std::sqrt(d)*std::sqrt(d)!=d){ puts("NO"); return; }
    if(-b+std::sqrt(d)/2<0){ puts("NO"); return; }
    __writesp(std::min(-b+std::sqrt(d)/2,n/(-b+std::sqrt(d)/2)));
    __write(std::max(-b+std::sqrt(d)/2,n/(-b+std::sqrt(d)/2)));
}

signed main(){


    freopen("decode.in","r",stdin);
    freopen("decode.out","w",stdout);

    int T=__read();
    while(T--){
        input();
        work();
    }
}

解析 二分法

二分 p，然后算出 q，通过上面的式子判断答案是否正确。

如果 pq<n，说明小了，往右找，反之。

代码 二分法

注意二分边界。

#include<bits/stdc++.h>

#define int long long
#define fore(i,x,n) for(int i=x;i<=n;i++)

const int MAXX=10005;
const int mod=1;

inline int __read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

inline void __write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) __write(x/10);
    putchar(x%10+'0');
}

inline void __writesp(int x){
    __write(x);
    putchar(' ');
}

int n,e,d;

inline void input(){
    n=__read(); d=__read();
    e=__read();
}

inline void work(){
    int d=n-e*d+2;
    int l=1,r=d/2;
    while(l<=r){
        int mid=l+((r-l)/2); 
        // 防止 mid 爆 long long
        if(mid*(d-mid)<n) l=mid+1;
        else r=mid-1;
    }
    if(l*(d-l)!=n) puts("NO");
    else{ __writesp(l); __write(d-l); }
}

signed main(){

    freopen("decode.in","r",stdin);
    freopen("decode.out","w",stdout);

    input();
    work();

}