【牛客 - 185A】无序组数 （思维，数学，因子个数）

题干：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

给出一个二元组（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

输入

复制

1 4 6

输出

复制

11

说明

样例解释： 二元组如下： (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组

 

解题报告：

   题目要求无序对，我们先想象成有序对，然后再减去重复的，就是最终答案了。

   有序对很好求，先打表出每一个数的因子个数，然后a和b的因子数相乘，就是有序对的个数，然后减去他俩最大公约数的因子个数（也就是重复了一次的个数）（此处用组合数公式去算，也就是C(n,2)。），得到的就是答案了。

AC代码：

#include<bits/stdc++.h> using namespace std; int d[100010]; int T; int main(){for(int i=1;i<100010;i++)for(int j=i;j<100010;j+=i)d[j]++;scanf("%d",&T);for(;T--;){int a,b;scanf("%d%d",&a,&b);printf("%d\n",d[a]*d[b]-d[__gcd(a,b)]*(d[__gcd(a,b)]-1)/2);}return 0; }

 

总结

以上是生活随笔为你收集整理的【牛客 - 185A】无序组数 （思维，数学，因子个数）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。