爱奇艺-笔试刷题2018-07-21

题目描述：

/**
考虑定义在两正整数上的函数SSR(平方根之和的平方):
SSR(A, B) = (sqrt(A) + sqrt(B))^2。牛牛对函数值为整数的情况很感兴趣。
现在给定整数n和m,
请帮助牛牛计算有序对(A, B)的数量,
 满足1 ≤ A ≤ n, 1 ≤ B ≤ m
而且SSR(A, B)是一个整数。
输入描述:
输入包括两个整数n和m(1 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5)
输出描述:
输出一个整数,表示满足条件的有序对对数。
输入例子1:
3 8
输出例子1:
5
*/

思路如下：

其实就是找给定范围内的数，组成对(A, B)使得 AB为完全平方数
枚举A B
首先建立素数表
然后对于没一个A建立一个其特征
这个特征是一个整数feature=1，这么定义：
对于A的所有质因数pi若其指数为奇数,feature=pi
为了提高一点效率这个feature应该选用
feature[A]表示A特征
map<int feature, int freq>表示在某个范围内出现这样feature的频率
注意这里的feature也最多是10^5 因为一个数A的feature<=A
若一个数的feature=1表示这个数是一个完全平方数
(注意：由于feature中素因子都是只有一次项，那么就是说不可能有A和B的feature相同，但是却奇次幂素因子却不能匹配)
那么B如果有和A同样的feature表示，A，B中那些为奇数幂的质因子可以配对成偶数
求feature的时间O(logN)
最大时间复杂度O(NlogN)

代码如下：

#include<stdio.h>
#include<iostream>
#include<vector>
 
#define MAX 100005
 
using namespace std;
 
//featureOfNum[num]表示num这个数的feature、
//统计这个featureOfNum可以一次性计算好范围较大的那一段，两段可以共用
int featureOfNum[MAX];
//featureToFreqMap[feature]表示feature这个特征出现的频率
//注意统计这个featueToFreqMap仅仅统计范围更小的那一段
int featureToFreqMap[MAX];
 
//建立素数表
vector<int> BuildPrimesTable(int n)
{
    vector<int> primes;
    bool *isNotPrime=new bool[n+1];
    isNotPrime[0]=isNotPrime[1]=true;
    for(int i=2; i<=n; i++)
        isNotPrime[i]=false;
    for(int i=2; i<=n; i++){
        if(isNotPrime[i]){
            continue;
        }
        primes.push_back(i);
        for(int j=i+i; j<=n; j+=i)
            isNotPrime[j]=true;
    }
    return primes;
}
 
//对num进行质因数分解然后解决，得出num中那些奇次幂的因子的积
int GetFeature(int num, vector<int>& primes)
{
    int feature=1;
    int tempNum=num;
    for(int i=0; i<primes.size(); i++){
        int prime=primes[i];
        if(tempNum<prime)
            break;
        int powCnt=0;
        while(tempNum%prime==0){
            tempNum/=prime;
            powCnt++;
        }
        //为奇次幂的乘到feature中
        if(powCnt%2)
            feature*=prime;
    }
    return feature;
}
 
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    //保证m是比较小的那一段
    if(m>n)
        swap(m, n);
    //先建立好最大范围内的素数表
    vector<int> primes;
    primes=BuildPrimesTable(n);
//    //测试
//    for(int i=0; i<primes.size(); i++)
//        printf("%d ", primes[i]);
//    printf("\n");
    //建立featureOfNum和featureToFreqMap
    for(int i=1; i<=n; i++){
        int feature=GetFeature(i, primes);
//        printf("i: %d, feature: %d\n", i, feature);
        if(i<=m){
            featureToFreqMap[feature]++;
        }
        featureOfNum[i]=feature;
    }
    long long totalPairs=0;
    for(int i=1; i<=n; i++){
        int feature=featureOfNum[i];
        totalPairs+=(long long)featureToFreqMap[feature];
    }
    printf("%lld", totalPairs);
    return 0;
}