IEEE全球极限编程大赛10.0题目题解：给出数字N，A，B，求出A,B之间与N互质的数的和（数据范围大）

题目

题目来源 第10届IEEE极限编程大赛

https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/inti-sets

In order to motivate his Peruvian students, a teacher includes words in the Quechua language in his math class.

Today, he defined a curious set for a given positive integer N. He called this set, an Inti set, and defined it as the set of all positive integer numbers that have the number 1 as their single common positive divisor with number N.

The math class about Inti sets was amazing. After class, the students try to challenge to teacher. They each ask questions like this: "Could you tell me the sum of all numbers, between A and B (inclusive), that are in the Inti set of N?"

Since the teacher is tired and he's sure that you are the best in class, he wants to know if you can help him.

Input Format

The first line of input contains an integer Q, 1 ≤ Q ≤ 20, representing the number of students. Each of the next Qlines contain three space-separated integers N, A and B, which represent a query.

Constraints

1 ≤ A ≤ B ≤ N ≤ 10^12

Output Format

The output is exactly Q lines, one per student query. For each query you need to find the sum of all numbers between A and B, that are in the Inti set of N, and print the sum modulo 1000000007.

Sample Input

2
12 5 10 
5 1 4

Sample Output

12
10

Explanation

In the sample input, Q = 2, so you have to answer two questions:

In the first question N = 12, A = 5 and B = 10. So you have to find the sum of all numbers between 5 and 10, that are in the Inti set of 12.

Inti set ( 12 ) = { 1, 5, 7, 11, 13, ... }

2 and 4 are not in the Inti set (12) because 12 and these numbers are also divisible by 2.

3 and 9 are not in the Inti set (12) because 12 and these numbers are also divisible by 3.

The numbers in the Inti set, which are in the query's range, are 5 and 7, so answer is ( 5 + 7 ) MOD 1000000007 = 12

In the second question, the numbers in the Inti set of 5 between 1 and 4 are: 1, 2, 3, 4; so the answer is ( 1 + 2 + 3 + 4 ) MOD 1000000007 = 10

解题思路

在上一篇文章当中我们完成了数据较小时的实现，但是显然直接求和对于数据量大时会超时，对于该题可以利用容斥原理来进行计算：
eg:若N=12,A=5,B=10;定义Sum(A,B,x),该函数可以计算A,B之间是x的倍数的数的和，则要计算5~10之间与12互质的数的和result，因为12的质因数为2,3，,所以result=Sum(5,10,1)-Sum(5,10,2)-Sum(5,10,3)+Sum(5,10,6)（容斥原理）

注意在计算中要时刻记得进行取模运算且保持数据为正

找出不大于x的所有质数

因为本题N<=10^12,所以我们直接将不大于10^6的质数一次性找出来放入数组pri当中，后续对于不同的N的输入直接在该数组当中找其质因数

代码：

void findx(long long x,vector<long long> &pri){
    vector <bool> num(x,1);
    for(long long i=2;i<x;i++){
        if(num[i]==true){
            pri.push_back(i);
            for(long long z=2;z*i<x;z++){
                num[z*i]=false;
            }
        }
    }
} 

找出N的所有质因数

在已经找出的质数集合pri当中，用试触除法找出N的所有质因数并将其放入数组s当中，因为N的质因数肯定小于等于根号N，所以不需要遍历pri,只需要遍历到小于等于根号N时就可以了（因为我用的long long 类型，是一种整数类型，所以用的根号N+1为分界）

代码：

void search(long long N,vector<long long> &s,vector<long long> &pri){
    long long t=sqrt(N)+1;
    for(long long i=0;i<pri.size();i++){
        if(N%pri[i]==0){
            s.push_back(pri[i]);
            continue;
        }
        if(pri[i]>t)break;
    }
} 

自定义函数求A,B之间是质因数的倍数的数的和

这里要用两个数学知识：等差数列求和、模运算

在等差数列求和当中需要注意首项和末项该怎么取；因为最终要求的也是取模后的值，所以在计算过程但中需要时刻记得取模，不要有数据溢出

代码：

int Sum(long long A,long long B,long long x){
    long long a=(A+x-1)/x;//向上取整
    long long b=B/x;//向下取整 
    long long s=0;
    long long result=0;
    if((a+b)%2==0){
        s=(((a+b)/2)%MAX)*((b-a+1)%MAX);//模运算，保证数据在规定范围内 
    }
    else{
        s=((a+b)%MAX)*(((b-a+1)/2)%MAX);
    }
    result=(s%MAX)*(x%MAX)%MAX;
    return result;
} 

遍历质因数组合（容斥原理）

以N=12为例，它有2,3两个质因数，则它的质因数组合共有2^2=4种，即我们可以用移位运算来计算它质因数组合的种数number，然后从零开始遍历所有的质因数组合（以二进制数第i位为1表示s[i]取得，可以用按位与运算‘&’来操作）

代码：

for(long long x=0;x<number;x++){
            long long re=1;
            int cont=0;
            for(long long j=0;j<s.size();j++){
                if((x>>j)&1){//第i位是否为1 
                    re*=s[j];
                    cont++;
                }
            }
        //容斥原理 
            if(cont%2==0){
                result[i]=(result[i]+Sum(A,B,re)+MAX)%MAX;
            }
            else{
                result[i]=(result[i]-Sum(A,B,re)+MAX)%MAX;
            }
        } 
    }

完整代码

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define MAX 1000000007

//找出不大于x的所有质数 
void findx(long long x,vector<long long> &pri){
    vector <bool> num(x,1);
    for(long long i=2;i<x;i++){
        if(num[i]==true){
            pri.push_back(i);
            for(long long z=2;z*i<x;z++){
                num[z*i]=false;
            }
        }
    }
} 

//找出N的所有质因数
void search(long long N,vector<long long> &s,vector<long long> &pri){
    long long t=sqrt(N)+1;
    for(long long i=0;i<pri.size();i++){
        if(N%pri[i]==0){
            s.push_back(pri[i]);
            continue;
        }
        if(pri[i]>t)break;
    }
} 

//求出在A,B之间是质因数的倍数的数的和（用等差数列和求模的方法）
int Sum(long long A,long long B,long long x){
    long long a=(A+x-1)/x;//向上取整
    long long b=B/x;//向下取整 
    long long s=0;
    long long result=0;
    if((a+b)%2==0){
        s=(((a+b)/2)%MAX)*((b-a+1)%MAX);//模运算，保证数据在规定范围内 
    }
    else{
        s=((a+b)%MAX)*(((b-a+1)/2)%MAX);
    }
    result=(s%MAX)*(x%MAX)%MAX;
    return result;
} 

int main(){
    long long Q;
    cin>>Q;
    vector<long long>result(20,0);
    vector<long long>pri;
    findx(1000000,pri);
    for(long long i=0;i<Q;i++){
        long long N,A,B;
        cin>>N>>A>>B;
        vector<long long>s;
        search(N,s,pri);
        long long number=(long long)1<<(s.size());
        //遍历所有的质因数组合
        for(long long x=0;x<number;x++){
            long long re=1;
            int cont=0;
            for(long long j=0;j<s.size();j++){
                if((x>>j)&1){//第i位是否为1 
                    re*=s[j];
                    cont++;
                }
            }
        //容斥原理 
            if(cont%2==0){
                result[i]=(result[i]+Sum(A,B,re)+MAX)%MAX;
            }
            else{
                result[i]=(result[i]-Sum(A,B,re)+MAX)%MAX;
            }
        } 
    }
    for(long long i=0;i<Q;i++)
    cout<<result[i]<<endl;
    return 0; 
} 

如有错误或者需要改进的地方，敬请指正