IEEEXtreme 10.0 - Inti Sets

时间:2022-10-12 17:11:00

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

Xtreme 10.0 - Inti Sets

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

题目解析

显然直接求和会超时,可以用容斥原理解决。

用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

注意需要使用取余运算避免溢出。

复杂度分析

IEEEXtreme 10.0 - Inti Sets

如果有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 - ) / x; // 上取整
long long bb = b / x; // 下取整 long long sum; // sum会超过long long的表示范围
if( (aa + bb) % == ) {
sum = (((aa + bb) / ) % MAXN) * ((bb - aa + ) % MAXN);
} else {
sum = ((aa + bb) % MAXN) * (((bb - aa + ) / ) % MAXN);
} return ((sum % MAXN) * (x % MAXN)) % MAXN;
} // 求不大于max的所有素数
// 使用筛选法
void getPrimes(vector<long long> &primes, long long max) {
vector<bool> nums(max, );
for(long long i=; i<max; i++) {
if(nums[i] == false) {
primes.push_back(i);
for(int n=*i; n<max; n+=i) {
nums[n] = true;
}
}
}
} // 对数x进行质因数分解
void getFactors(long long x, vector<long long> &factors, vector<long long> &primes) {
int i = ;
while(x > && i < primes.size()) {
if(x % primes[i] == ) {
factors.push_back(primes[i]);
while(x % primes[i] == ) x /= primes[i];
}
i++;
}
// 小于10^12的数最对有一个大于10^6的质因数
if(x > ) {
factors.push_back(x);
}
} int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
vector<long long> primes;
getPrimes(primes, ); int T;
cin >> T;
for(int t=; t<T; t++) {
long long x, a, b;
cin >> x >> a >> b;
long long result = ;
vector<long long> factors;
getFactors(x, factors, primes); int factorCount = factors.size();
long long binMax = (long long) << factorCount; // 遍历所有的质因数组合
for(long long bin=; bin<binMax; bin++) {
long long factor = ;
int factorC = ;
for(int i=; i<factorCount; i++) {
if( (bin >> i) & ) {
factor *= factors[i];
factorC ++;
}
} if(factorC % == ) {
result = (result + sumOver(a, b, factor) + MAXN) % MAXN;
}
else {
result = (result - sumOver(a, b, factor) + MAXN) % MAXN;
}
} cout << result << endl;
} return ;
}

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

IEEEXtreme 10.0 - Inti Sets的更多相关文章

  1. IEEEXtreme 10&period;0 - Painter&&num;39&semi;s Dilemma

    这是 meelo 原创的 IEEEXtreme极限编程比赛题解 Xtreme 10.0 - Painter's Dilemma 题目来源 第10届IEEE极限编程大赛 https://www.hack ...

  2. IEEEXtreme 10&period;0 - Ellipse Art

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Ellipse Art 题目来源 第10届IEEE极限编程大赛 https://www.hackerrank ...

  3. IEEEXtreme 10&period;0 - Counting Molecules

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Counting Molecules 题目来源 第10届IEEE极限编程大赛 https://www.hac ...

  4. IEEEXtreme 10&period;0 - Checkers Challenge

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Checkers Challenge 题目来源 第10届IEEE极限编程大赛 https://www.hac ...

  5. IEEEXtreme 10&period;0 - Game of Stones

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Game of Stones 题目来源 第10届IEEE极限编程大赛 https://www.hackerr ...

  6. IEEEXtreme 10&period;0 - Playing 20 Questions with an Unreliable Friend

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Playing 20 Questions with an Unreliable Friend 题目来源 第1 ...

  7. IEEEXtreme 10&period;0 - Full Adder

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Full Adder 题目来源 第10届IEEE极限编程大赛 https://www.hackerrank. ...

  8. IEEEXtreme 10&period;0 - N-Palindromes

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - N-Palindromes 题目来源 第10届IEEE极限编程大赛 https://www.hackerra ...

  9. IEEEXtreme 10&period;0 - Mysterious Maze

    这是 meelo 原创的 IEEEXtreme极限编程大赛题解 Xtreme 10.0 - Mysterious Maze 题目来源 第10届IEEE极限编程大赛 https://www.hacker ...

随机推荐

  1. windows10 technical preview 无法激活

  2. BZOJ 3170 松鼠聚会(XY坐标)

    题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=3170 题意:给出二维平面上n个点 (xi,yi).求一点t(1<=t<=n) ...

  3. 【C&num;】索引器

    索引器允许类或者结构的实例按照与数组相同的方式进行索引取值,索引器与属性类似,不同的是索引器的访问是带参的. 索引器和数组比较: (1)索引器的索引值(Index)类型不受限制 (2)索引器允许重载 ...

  4. SqlServer 数据库进行定时自动的执行脚本

    需求:数据库进行自动执行脚本操作,有些数据库操作就不需要写程序来定时执行,完全可以交给我们SqlServer客户端代理来做,下面的步骤,我是结合前一篇文章的SqlServer不同服务器数据库之间数据传 ...

  5. mysql查询字段值为数字

    原文:mysql查询字段值为数字 我想查询字段值为数字的sql如下:select * from tj_item_result where tj_value REGEXP '^[0-9]'

  6. C&plus;&plus;中L和&lowbar;T&lpar;&rpar;之区别

    字符串前面加L表示该字符串是Unicode字符串._T是一个宏,如果项目使用了Unicode字符集(定义了UNICODE宏),则自动在字符串前面加上L,否则字符串不变.因此,Visual C++里边定 ...

  7. jmeter元件执行顺序及简介

    最近在学习Jmeter,在进行实操之前,先查看了官方文档.因为官方文档是英文的,为了方便以后查看,自己翻译了一部分,中间个别地方根据自己的理解简单地翻译了部分.如果翻译等有问题,欢迎指正. 一.执行顺 ...

  8. wordpress和数据库的连接

    1.首先在数据库里创建wordpress数据库 2.在网页上配置WordPress,安装WordPress 如上配置不对,提交时提示了错误,于是我选择了root用户 123456, 3.提交后,连上了 ...

  9. Centos6&period;5下rsync&plus;inotify的配置详解

    Centos 6.5配置rsync+inotify实现文件实时同步 1.安装rsync(两台机器执行相同的步骤) yum install gcc yum install rsyncd xinetd - ...

  10. 如何修改路由器的登录IP地址?

    如何修改路由器的登录IP地址? 因为有多个路由器,为了区分不同路由器,我们可以修改它的登录IP,而且修改后,可以在连接的电脑上直观地知道所连接的是哪一台路由器 买回来的路由器,一般默认的登录地址是19 ...