首页 > 试题广场 >

小红的区间选数乘积

[编程题]小红的区间选数乘积
  • 热度指数：228 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一个正整数x，她希望在区间[l,r]中选择一个正整数y，满足x*y是完全平方数。小红想知道有多少种选择方案？

共有q次询问。

输入描述:
第一行输入一个正整数q，代表询问次数。
接下来的q行，每行输入三个正整数x,l,r，代表一次询问。
1\leq q\leq 10^4
1\leq x \leq 10^{14}
1\leq l \leq r \leq 10^{14}


输出描述:
输出q行，每行输出一个整数，代表询问的答案。
示例1

输入

2
2 6 9
6 6 36

输出

1
2

说明

对于第一组测试数据，只有选择 8 这一个方案，2\times 8 = 16 = 4^2 。
对于第二组测试数据，选择 6 和 24 均是合法的。

算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 14:04:13
题目链接 小红的区间选数乘积 题目描述 给定 次询问，每次询问给出三个正整数 。需要找到在区间 中有多少个正整数 ，满足 是一个完全平方数。数据范围为 。 解题思路 一个数是完全平方数，当且仅当其所有质因子的指数都是偶数。为了让 成为完全平方数， 的作用就是“补全” 中那些指数为奇数的质因 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

基础数学 数论
来自：2024年秋招-蚂蚁集...
难度：
0条回答 558浏览

热门推荐

相关试题

小红的区间选数乘积

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号