要证明一个东西：若\forall x,y \in \mathbb{N}, N \mid A_0 x+B_0 y，则A \equiv A_0 i ~(mod N), ~B \equiv B_0 i ~(mod N), ~(0 \le i < N)是N \mid Ax+By的充要条件。
　　证明：
1)充分性：显然。
2)必要性：
若N \mid A_0 x+B_0 y，则 N \mid Ax+By
=> 若A_0 x+B_0 y \equiv 0 ~(mod N)，则(A-A_0 i)x+(B-B_0 i)y \equiv 0 ~(mod N)
=> \left\{\begin{array}{l}A \equiv A_0 \cdot (i+1) ~(mod N)\\ B \equiv B_0 \cdot (i+1) ~(mod N)\end{array}\right.
即 \left\{\begin{array}{l}A \equiv A_0 \cdot i ~(mod N)\\ B \equiv B_0 \cdot i ~(mod N)\end{array}\right.
　　Submit 1: WA on 1。听说这题特殊情况非常多，哪些是特殊情况呢？FT……我忘了输出(A,B)的个数了。
　　Submit 2: WA on 1。漏掉了一种情况——A=0，我不是把(A,B)全求出来之后再排序，而是直接放hash table里，A=0我的hash就失败了。
　　Submit 3: WA on 4。补上了A=0却漏掉了(A,B,N)>1。新的hash（用list解决冲突）要解决这个问题需要证明另外一个命题，而且本身的效率下降很多，还是换回原来那个，然后特殊处理A=0吧。
　　原来的hash是基于这样的想法：对于A>0，不存在B1≠B2而(A,B1),(A,B2)同时满足条件。所以可以开一个表，用pair[a]=b表示(a,b)满足条件。
　　Submit 4: WA on 11。不仅A=0是特殊的，A=kN也是特殊的。编码上也出了点问题，if语句嵌套写错了，把其中一组改成三元运算符。
　　Submit 5: WA on 11。想不出问题出在什么地方，暂且换一种方法：把(A,B)全求出来之后再排序。
　　Submit 6: WA on 1。pair[r++]=(a*i%n)*10000+b*i%n; 即把(a,b)当作10000进制数字存储，是错误的。必须当作10001进制存储，不知道为什么，难道a,b不是小于10000的么？
　　Submit 7: AC。AC也没用……
　　Submit 5的问题有了一点眉目，写了个判断hash冲突的程序上去，果然得到hash有冲突，即“对于A≠kN，不存在B1≠B2而(A,B1),(A,B2)同时满足条件”是错误的，但为什么是错误的呢？
　　Submit 6的问题解决了，*10000是正确的，我提交的程序可能有笔误。但最后的程序还是改了，分别利用高16位和低16位存a,b。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

//注意这个程序是错的
//WA on 11
#include <cstdio>
#include <algorithm>
using namespace std;
 
int main()
{
    int pair[10000],n,a,b,r(0);
    fill(pair,pair+10000,-1);
    scanf("%d%d%d",&n,&a,&b);
    bool swaped(!(a%n));
    if (swaped) swap(a,b);
    for (int i(0);i<n;i++) if (pair[a*i%n]>0 && pair[a*i%n]!=b*i%n) return 4; else pair[a*i%n]=b*i%n;
    for (int i(0);i<n;i++) r+=(pair[i]>=0);
    printf("%d\n",r);
    if (swaped) for (int i(0);i<n;i++) pair[i]>=0?printf("%d %d\n",pair[i],i):0;
    else for (int i(0);i<n;i++) pair[i]>=0?printf("%d %d\n",i,pair[i]):0;
    return 0;
}
?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//AC
#include <cstdio>
#include <algorithm>
using namespace std;
 
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
 
int main()
{
    int pair[10000];
    int n,a,b,r;
    scanf("%d%d%d",&n,&a,&b);
    r=n/gcd(gcd(a,b),n);
    for (int i(0);i<r;i++) pair[i]=(a*i%n<<16)+b*i%n;
    sort(pair,pair+r);
    printf("%d\n",r);
    for (int i(0);i<r;i++) printf("%d %d\n",pair[i]>>16,pair[i]&0xffff);
    return 0;
}