本文主要是介绍zzuli 1902 (985的因子对难题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
打表 985的因子对难题
Description
985有n个正整数，他想知道存在多少个不同的因子对(a[i], a[j])使得
1 <= i, j <= n && i != j && a[j] % a[i] == 0，其中i和j是元素的下标。
特别地，他认为（a[i]，a[j]）与（a[j]，a[i]）是一样的因子对。
Input
第一行输入一个整数t，代表有t组测试数据。
每组数据占两行，第一行输入一个n代表元素个数，下面一行输入n个整数a[]。
注：1 <= t <= 30，1 <= n <= 1e5，1 <= a[] <= 1e6。
Output
一个整数代表最后的答案。
Sample Input
2
5
1 2 3 4 5
5
2 2 2 2 2
Sample Output
5
10
题解：辣鸡看到这题完全没思路。思路是，记录每个数字以及出现的次数，利用打表找出每个数存在的因子个数，若存在n个相同的数字，该数字的因子对个数为n*(n-1)/2，还需要加上他的因子个数，因为这wa了，打表也不熟练。
//因子对
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;int main(){int t,n,i,j,y;int num[101010];int f[101010];scanf ("%d",&t);while (t--){scanf ("%d",&n);int maxi=0;long long sum=0;memset (num,0,sizeof(num));memset (f,0,sizeof(f));for (i=1;i<=n;i++){scanf ("%d",&y);num[y]++;//记录该数字出现的个数maxi=max(maxi,y);//找出最大的数字，供下边循环找因子使用}for (i=1;i<=maxi;i++){if (!num[i]) continue;for (j=i+i;j<=maxi;j+=i){//打表，还需要再熟练f[j]+=num[i];}}for (i=1;i<=maxi;i++){if (num[i]){if (num[i]>1)sum+=num[i]*(num[i]-1)/2;sum+=num[i]*f[i];//这一步不论是不是存在多个相同数字，都有用}}printf ("%lld\n",sum);}return 0;
}这篇关于zzuli 1902 (985的因子对难题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
