牛客OI赛制测试赛2 A 无序组数

链接：https://www.nowcoder.com/acm/contest/185/A
来源：牛客网

题目描述

给出一个二元组（A,B）
求出无序二元组（a,b）使得（a|A，b|B）的组数
无序意思就是(a,b)和(b,a) 算一组.

输入描述:

第一行数据组数 T（1≤T≤10000）
接下来T行，每行两个正整数 A,B（1≤A,B≤10000）

输出描述:

共T行，每行一个结果

输入例子:

1

4 6

输出例子:

-->

示例1

输入

复制

1

4 6

输出

复制

说明

样例解释：
二元组如下：
(1,1)(1,2)(1,3)(1,6)
(2,1)(2,2)(2,3)(2,6)
(4,1)(4,2)(4,3)(4,6)
共12组.
无序二元组如下：

(1,1)(1,2)(1,3)(1,6)
(2,2)(2,3)(2,6)
(4,1)(4,2)(4,3)(4,6)
共11组

$n^2$的暴力应该无脑写吧，就不在此多说了，直接讲正解。
a和b$\le$10000,我不知道在一个循环里，for(i=1 ->max(a,b))，然后判断i与a，b的大小这样来枚举a，b的因数可不可以过，$1000 \times 10000$说不定可以试试。
我们来说我比较安全的解法。
我们需要先找出A,B每个数的因子个数，当然我们需要枚举，假设我们在枚举找出A的一个a，那么A/a又何尝不是另一个因子，这样的话我们找到一个因子，因子数加2，当然这个数最大为

为$\sqrt A \times \sqrt A$，所以我们对于每个T最多枚举$ \sqrt A + \sqrt B$次，当然对于$\sqrt A$是A 的因子这种$i = A/ i $的情况需要特殊判断一下，只能因字数加1.

对于A的每个因子，用一个数组标记一下，为了方便判断B的因子中有多少个与之相同的数的个数。

同样的方法，我们求出B的同时记录有多少个相同的因子。

下面来说找出相同的因子数的个数怎么用。

设A的因字数为：1 3 4 5

设B的因子数为：1 4 5 7

我们用A的因子来配B的因子：1(4种),3(4种),4(3种)，5(2种)

我们发现若这个数不是公共因子，那么对于每个数情况个数都为B的因子数量，若为公共因子，第一次出现情况数为B的因字数，第二次出现为B的因字数-1，第三次-2...。

那么答案就可以计算为：A的因子的个数$\times$B的因子的个数-1-2-...-(公共因子数-1)。

对于-1-2..这部分可以稍微优化一下，作用不是很大啦。

if(sumv%==)sumv=(sumv+)*(sumv/);

else sumv=(sumv+)*(sumv/)+;    //sumv表示公共因子个数。

代码：

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

int T,a,b,suma,sumb,sumv;

bool vis[];

int main()

{

    scanf("%d",&T);

    while(T--)

    {

        memset(vis,,sizeof(vis));

        suma=sumb=sumv=;

        scanf("%d%d",&a,&b);

        int p=sqrt(a);

        int q=sqrt(b);

        for(int i=; i<=p; i++)

        {

            if(a%i==)

            {

                if(a/i==i)suma+=,vis[i]=;

                else suma+=,vis[i]=vis[a/i]=;

            }

        }

        for(int i=; i<=q; i++)

        {

            if(b%i==)

            {

                if(b/i==i)sumb+=,sumv+=vis[i];

                else sumb+=,sumv+=vis[i],sumv+=vis[b/i];

            }

        }

        sumv--;

        if(sumv%==)sumv=(sumv+)*(sumv/);

        else sumv=(sumv+)*(sumv/)+;

        printf("%d\n",suma*sumb-sumv);

    }

}

巴特西