UCF Local Programming Contest 2016 H. Count the Dividing Pairs（整除对数）

Number Theory provides many fascinating properties. You have most likely written programs dealing with different groups of numbers such as Prime, Perfect, Amicable, Happy, Powerful, and Untouchable numbers, just to name a few. In this problem, you’ll attack yet another fascinating property of numbers, one dealing with pairs of numbers. 

An integer D is said to be a proper divisor of an integer N if D ≠ N and there exist an integer Q such that N = Q * D. For example, 4 is a proper divisor of 8 and 5 is a proper divisor of 15, but 9 is not a proper divisor of 9 and 6 is not a proper divisor of 8. Note that zero is not a proper divisor of any number but all numbers (except zero) are proper divisors of zero. 

We will call (D, N) as defined above “proper dividing pairs”. 

The Problem: 

Given a list of integers A = {A1, A2, …, Ap}, you are to determine (count) the number of proper dividing pairs (Ai, Aj), where 1 ≤ i, j ≤ p. 

The Input: 

The first input line contains a positive integer, n, indicating the number of test cases to process. Each test case starts with an integer, p (2 ≤ p ≤ 1000,000), indicating the number of integers in the list. The following input line will provide p integers, Ai (0 ≤ Ai ≤ 10,000,000). 

The Output: 

For each test case, print "Test case #t: m", where t indicates the case number starting with 1 and m indicates the number of proper dividing pairs. Leave a blank line after the output for each test case.

Note that, as illustrated in Sample Input/Output, duplicate values in the input list are considered as different elements in the list and they each contribute to the total count (proper dividing pairs).

样例输入复制

5 
3 
1 2 3 
4 
1 2 3 1 
2 
7 5 
3 
29 0 17 
10 
32 16 8 4 2 2 4 8 16 32

样例输出复制

Test case #1: 2 

Test case #2: 4 

Test case #3: 0 

Test case #4: 2 

Test case #5: 40

题意：

求数列中能够整除的对数，不包括自己整除自己。

思路：

用数组num[i]标记 i 出现过多少次，暴力枚举整除对

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const int N = 1e7 + 10;

int num[N];

int main()
{
    int t, n, kcase = 0, a;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        memset(num, 0, sizeof(num));
        int maxx = -1;
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d", &a);
            num[a]++;
            if(maxx < a)
                maxx = a;
        }
///        ll ans = (ll)(num[0] * (n - num[0]) + num[1] * (n - num[0] - num[1]));   ///WA 爆int了？？？？
        ll ans = (ll)num[0] * (n - num[0]) + (ll)num[1] * (n - num[0] - num[1]);    ///AC
        for(int i = 2; i <= maxx / 2; ++i)
        {
            if(num[i])
            {
                for(int j = i + i; j <= maxx; j += i)
                {
                    if(num[j])
                    {
                        ans += (ll)num[i] * num[j];
                    }
                }
            }
        }
        printf("Test case #%d: %lld\n\n", ++kcase, ans);
    }
    return 0;
}