4494: G. Grade 2
内存限制：256 MB
时间限制：3 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
Kotsuki the Cat, together with FuuFuu and Pico, lives in the KFP apartment. As a teacher, Kotsuki needs to go to school every day to give lessons. One day, Kotsuki gives a math lesson to some grade 2 students in primary school, covering the following topics:
- Coprime: Two integers are coprime if the only positive integer that is a divisor of both of them is 1.
- Bitwise XOR (⊕): Bitwise XOR is a binary operation that takes two integers and performs the logical exclusive OR operation on each pair of corresponding bits of their binary forms. The result in each will be 1 if only one of the bits is 1, but will be 0 if both are 0 or both are 1. For example, 5⊕3=(101)2⊕(011)2=(110)2=6.
-
Given an integer x, for different intervals [l,r], please calculate the number of integers k within the interval satisfying kx⊕x and x are coprime. Formally, please calculate
输入格式
The first line contains two integers x (1 ≤ x ≤ 106) and n (1 ≤ n ≤ 105), where n indicates the number of intervals.
Each of the following n lines contains two integers l and r (1 ≤ l ≤ r ≤ 1012), indicating an interval [l,r].
Each of the following n lines contains two integers l and r (1 ≤ l ≤ r ≤ 1012), indicating an interval [l,r].
输出格式
For each interval, output the answer in a single line.
输入样例 复制
15 2
1 4
11 4514
输出样例 复制
2
2252
数据范围与提示
When x=15,
- k=1, gcd(kx⊕x,x)=gcd(15⊕15,15)=gcd(0,15)=15
- k=2, gcd(kx⊕x,x)=gcd(30⊕15,15)=gcd(17,15)=1
- k=3, gcd(kx⊕x,x)=gcd(45⊕15,15)=gcd(34,15)=1
- k=4, gcd(kx⊕x,x)=gcd(60⊕15,15)=gcd(51,15)=3