UVa

Luogu

Vjudge

分析

设 $R^2\equiv x\pmod N$ 。

因为 $r^2\equiv x\pmod N$ ,所以 $r^2-R^2\equiv0\pmod N$ 。

也就是 $(r+R)(r-R)\equiv 0\pmod N$ 。

设 $r+R\equiv a\pmod N,r-R\equiv b\pmod N$ ,那么有 $ab=N$ 。

设 $r+R=ax,r-R=by$ 。

于是有 $(r+R)+(r-R)=ax+by$ ,化简得到 $ax+by=2r$ 。

于是只需要枚举 $N$ 的约数 $a$ ,然后算出 $b=N/a$ ,即可通过 exgcd 算出对应的 $r$ 。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int x,n,r;
set<int> ans;

inline int exgcd(int a,int b,int& x,int& y) {
    if (!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,y,x); y-=a/b*x;
    return d;
}

inline void solve(int a,int b,int c) {
    int x,y,d=exgcd(a,b,x,y);
    if (c%d) return;
    x=x*c/d; x=(x%(b/d)+(b/d))%(b/d);
    int R=a*x-r,dlt=a*b/d;
    for (;R<n;R+=dlt)
        if (R>=0) ans.insert(R);
}

signed main() {
    int _=0;
    while (x=read(),n=read(),r=read()) {
        ans.clear();
        for (re int i=1;i*i<=n;++i) {
            if (n%i) continue;
            solve(i,n/i,r<<1);
            solve(n/i,i,r<<1);
        }
        printf("Case %lld:",++_);
        for (re int i:ans) printf(" %lld",i);
        puts("");
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 49 PM