Xtreme 10.0 - Inti Sets

这是 meelo 原创的 IEEEXtreme极限编程大赛题解

题目来源 第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

212 5 10 5 1 4

Sample Output

1210

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

题目解析
显然直接求和会超时，可以用容斥原理解决。
用sumOver(5, 10, 1)表示区间[5,10]内为1倍数的数
由于12的质因数为2, 3
sum(区间[5, 10]内与12互质的数) = sumOver(5, 10, 1) - sumOver(5, 10, 2) - sumOver(5, 10, 3) + sumOver(5, 10, 6)

可以通过区间[0,2^2)来遍历所有因式的组合，
数二进制形式的每一位代表是否存在该因数，1代表存在，0代表不存在，
因数的个数为偶数意味着和需要加上，为奇数意味着需要减去
00代表因数为1, 01代表因数为3, 10代表因数为2, 11代表因数为6

复杂度分析

如果有c个质因数，那么需要求2^c个数的和
求每一个和需要常数时间O(1)
数N，至多只有一个大于sqrt(N)的质因数，因此质因数的个数不超过log(sqrt(N))+1
总复杂度为O(sqrt(N))

程序
C++

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

#define MAXN 1000000007

// 区间[a,b]内，所有为x倍数数的和
long long sumOver(long long a, long long b, long long x) {
    long long aa = (a + x - 1) / x;
    long long bb = b / x;
    
    long long sum; // sum会超过long long的表示范围
    if( (aa + bb) % 2 == 0) {
        sum = (((aa + bb) / 2) % MAXN) * ((bb - aa + 1) % MAXN);
    } else {
        sum = ((aa + bb) % MAXN) * (((bb - aa + 1) / 2 ) % MAXN);
    }
    
    return ((sum % MAXN) * (x % MAXN)) % MAXN;
}

// 求不大于max的所有素数
// 使用筛选法
void getPrimes(vector<long long> &primes, long long max) {
    vector<bool> nums(max, 0);
    for(long long i=2; i<max; i++) {
        if(nums[i] == false) {
            primes.push_back(i);
            for(int n=2*i; n<max; n+=i) {
                nums[n] = true;
            }
        }
    }
}

// 对数x进行质因数分解
void getFactors(long long x, vector<long long> &factors, vector<long long> &primes) {
    int i = 0;
    while(x > 1 && i < primes.size()) {
        if(x % primes[i] == 0) {
            factors.push_back(primes[i]);
            while(x % primes[i] == 0) x /= primes[i];
        }
        i++;
    }
    // 小于10^12的数最对有一个大于10^6的质因数
    if(x > 1) {
        factors.push_back(x);
    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    vector<long long> primes;
    getPrimes(primes, 1000000);
    
    int T;
    cin >> T;
    for(int t=0; t<T; t++) {
        long long x, a, b;
        cin >> x >> a >> b;
        long long result = 0;
        vector<long long> factors;
        getFactors(x, factors, primes);
        
        int factorCount = factors.size();
        long long binMax = (long long)1 << factorCount;

        for(long long bin=0; bin<binMax; bin++) {
            long long factor = 1;
            int factorC = 0;
            for(int i=0; i<factorCount; i++) { 
                if( (bin >> i) & 1 ) {
                    factor *= factors[i];
                    factorC ++;
                }
            }

            if(factorC % 2 == 0) {
                result = (result + sumOver(a, b, factor) + MAXN) % MAXN;
            }
            else {
                result = (result - sumOver(a, b, factor) + MAXN) % MAXN;
            }
        }
        
        cout << result << endl;
    }
    
    return 0;
}

博客中的文章均为 meelo 原创，请务必以链接形式注明 本文地址