P3455 [POI2007]ZAP-Queries

    • 645通过
    • 1.2K提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 最大公约数,gcd 莫比乌斯反演 POI 2007 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    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希望得到你的帮助。

    输入输出格式

    输入格式:

    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.

    输出格式:

    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.

    输入输出样例

    输入样例#1: 复制
    2
    4 5 2
    6 4 3
    输出样例#1: 复制
    3
    2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。