[POI 2007]ZAP-Queries
Description
Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has alreadyfound out that whilst deciphering a message he will have to answer multiple queries of the form"for givenintegers $a$, $b$ and $d$, find the number of integer pairs $(x,y)$ satisfying the following conditions:
$1\le x\le a$,$1\le y\le b$,$gcd(x,y)=d$, where $gcd(x,y)$ is the greatest common divisor of $x$ and $y$".
Byteasar would like to automate his work, so he has asked for your help.
TaskWrite a programme which:
reads from the standard input a list of queries, which the Byteasar has to give answer to, calculates answers to the queries, writes the outcome to the standard output.
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。
Input
The first line of the standard input contains one integer $n$ ($1\le n\le 50\ 000$),denoting the number of queries.
The following $n$ lines contain three integers each: $a$, $b$ and $d$($1\le d\le a,b\le 50\ 000$), separated by single spaces.
Each triplet denotes a single query.
Output
Your programme should write $n$ lines to the standard output. The $i$'th line should contain a single integer: theanswer to the $i$'th query from the standard input.
Sample Input
2
4 5 2
6 4 3
Sample Output
3
2
题解
双倍经验。去掉容斥就好了,分析见超链接。
//It is made by Awson on 2018.1.21
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
#define writeln(x) (write(x), putchar('\n'))
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = ;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
}
void write(LL x) {
if (x > ) write(x/);
putchar(x%+);
} int a, b, k, mu[N+]; void get_mu() {
int isprime[N+], prime[N+], tot = ;
memset(isprime, , sizeof(isprime)); isprime[] = , mu[] = ;
for (int i = ; i <= N; i++) {
if (isprime[i]) mu[i] = -, prime[++tot] = i;
for (int j = ; j <= tot && i*prime[j] <= N; j++) {
isprime[i*prime[j]] = ;
if (i%prime[j]) mu[i*prime[j]] = -mu[i];
else {mu[i*prime[j]] = ; break; }
}
mu[i] += mu[i-];
}
}
LL cal(int a, int b) {
if (a > b) Swap(a, b); LL ans = ;
for (int i = , last; i <= a; i = last+) {
last = Min(a/(a/i), b/(b/i));
ans += (LL)(mu[last]-mu[i-])*(a/i)*(b/i);
}
return ans;
}
void work() {
read(a), read(b), read(k); writeln(cal(a/k, b/k));
}
int main() {
int t; read(t); get_mu();
while (t--) work();
return ;
}
最新文章
- php 中文繁简体转换
- SQL Server中的事务日志管理(9/9):监控事务日志
- 关于ArrayList 容量问题
- cocos2dx 3.x(TexturePacker进行图片加密)
- 在 SVG 中添加交互性
- UVa 409 Excuses, Excuses!
- c# 使用hook来监控鼠标键盘事件的示例代码
- iOS开发——新特性OC篇&;Swift 2.0新特性
- oracle数据库中,分天查询数目
- weekly review
- elasticsearch的rest搜索---对于相关度的大牛的文档
- 【 js 基础 】关于this
- ●POJ 1990 MooFest
- BZOJ1095(动态点分治+堆)
- pip 安装mysqlclient报错OSError: mysql_config not found
- Spring框架基础(下)
- Codechef SUMCUBE Sum of Cubes 组合、三元环计数
- LeetCode 961. N-Repeated Element in Size 2N Array
- 萌新 学习 vuex
- 在vue-cli生成的项目中使用karma+chrome进行单元测试