题意：

给定正整数a，b并且a与b互质且满足a<b。

在所有小于b的自然数构成的集合A = {1，2，3，… ，b-1}中，称(c,d),c,d∈A中，为一个有序数对简称序偶。

求c和d相乘后模b等于a的序偶有多少对。

思路：

打表大法好。

打表之后可以发现跟a无关，然后看到数列是这样子的

1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44…

在OEIS里查了一下，是欧拉函数，所以写一下就可以了。

那么如果没有OEIS那怎么办呢？或许应该积累一些常见数列？或许看了题目要互质和b-1就要想到欧拉函数？

正解：

考虑小于b的且与b互质的一个数x，那么x和1，2，…，b−1的乘积模b的结果必然还是1，2，…，b−1。

若x和b不互质，那么x和1，2，…，b−1的乘积模b的结果必然也与b不互质，而a与b互质，这说明此时对答案不成贡献。

所以答案就是phi(b)。

代码：

int euler(int n)
{
    int i,res=n;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)
                n=n/i;
        }
    }
    if(n>1)res=res/n*(n-1);
    return res;
}
int main()
{
    int t,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",euler(b));
    }
    return 0;
}