Count the Values of k

目录

题目总览

思路

参考代码

原题链接: CF1933C Turtle Fingers: Count the Values of k


题目总览

# Turtle Fingers: Count the Values of k

## 题面翻译

给你三个**正**整数 $a$ 、 $b$ 和 $l$ ( $a,b,l>0$ )。

可以证明,总有一种方法可以选择**非负**(即 $\ge 0$ )的整数 $k$ 、 $x$ 和 $y$ ,使得 $l = k \cdot a^x \cdot b^y$ .

你的任务是找出所有这些方法中 $k$ 的不同可能值的个数。

**输入**

第一行包含整数 $t$ ( $1 \le t \le 10^4$ ) 

接下来的 $t$ 行包含三个整数 $a$ 、 $b$ 和 $l$ ( $2 \le a, b \le 100$ 、 $1 \le l \le 10^6$ )

**注**

在第一个测试案例中, $a=2, b=5, l=20$ . $k$ (及相应的 $x,y$ )的可能值如下:

- 选择 $k = 1, x = 2, y = 1$ 。然后选择 $k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l$ 。
- 选择 $k = 2, x = 1, y = 1$ 。然后是 $k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l$ 。
- 选择 $k = 4, x = 0, y = 1$ 。然后选择 $k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l$ 。
- 选择 $k = 5, x = 2, y = 0$ 。然后选择 $k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l$ 。
- 选择 $k = 10, x = 1, y = 0$ 。然后选择 $k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l$ 。
- 选择 $k = 20, x = 0, y = 0$ 。然后选择 $k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l$ 。

在第二个测试案例中,选择 $a=2, b=5, l=21$ 。注意 $l = 21$ 不能被 $a = 2$ 或 $b = 5$ 整除。因此,我们只能设置 $x = 0, y = 0$ ,即对应于 $k = 21$ 。

第三个测试情形是 $a=4, b=6, l=48$ 。 $k$ 的可能值(以及相应的 $x,y$ )是(和对应的 $x,y$ 的可能值如下:

- 选择 $k = 2, x = 1, y = 1$ 。然后选择 $k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l$ 。
- 选择 $k = 3, x = 2, y = 0$ 。然后是 $k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l$ 。
- 选择 $k = 8, x = 0, y = 1$ 。然后选择 $k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l$ 。
- 选择 $k = 12, x = 1, y = 0$ 。然后选择 $k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l$ 。
- 选择 $k = 48, x = 0, y = 0$ 。然后选择 $k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l$ 。

## 题目描述

You are given three positive integers $ a $ , $ b $ and $ l $ ( $ a,b,l>0 $ ).

It can be shown that there always exists a way to choose non-negative (i.e. $ \ge 0 $ ) integers $ k $ , $ x $ , and $ y $ such that $ l = k \cdot a^x \cdot b^y $ .

Your task is to find the number of distinct possible values of $ k $ across all such ways.

## 输入格式

The first line contains the integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases.

The following $ t $ lines contain three integers, $ a $ , $ b $ and $ l $ ( $ 2 \le a, b \le 100 $ , $ 1 \le l \le 10^6 $ ) — description of a test case.

## 输出格式

Output $ t $ lines, with the $ i $ -th ( $ 1 \le i \le t $ ) line containing an integer, the answer to the $ i $ -th test case.

## 样例 #1

### 样例输入 #1

```

11
2 5 20
2 5 21
4 6 48
2 3 72
3 5 75
2 2 1024
3 7 83349
100 100 1000000
7 3 2
2 6 6
17 3 632043


```

### 样例输出 #1

```

6
1
5
12
6
11
24
4
1
3
24


```

## 提示

In the first test case, $ a=2, b=5, l=20 $ . The possible values of $ k $ (and corresponding $ x,y $ ) are as follows:

- Choose $ k = 1, x = 2, y = 1 $ . Then $ k \cdot a^x \cdot b^y = 1 \cdot 2^2 \cdot 5^1 = 20 = l $ .
- Choose $ k = 2, x = 1, y = 1 $ . Then $ k \cdot a^x \cdot b^y = 2 \cdot 2^1 \cdot 5^1 = 20 = l $ .
- Choose $ k = 4, x = 0, y = 1 $ . Then $ k \cdot a^x \cdot b^y = 4 \cdot 2^0 \cdot 5^1 = 20 = l $ .
- Choose $ k = 5, x = 2, y = 0 $ . Then $ k \cdot a^x \cdot b^y = 5 \cdot 2^2 \cdot 5^0 = 20 = l $ .
- Choose $ k = 10, x = 1, y = 0 $ . Then $ k \cdot a^x \cdot b^y = 10 \cdot 2^1 \cdot 5^0 = 20 = l $ .
- Choose $ k = 20, x = 0, y = 0 $ . Then $ k \cdot a^x \cdot b^y = 20 \cdot 2^0 \cdot 5^0 = 20 = l $ .

In the second test case, $ a=2, b=5, l=21 $ . Note that $ l = 21 $ is not divisible by either $ a = 2 $ or $ b = 5 $ . Therefore, we can only set $ x = 0, y = 0 $ , which corresponds to $ k = 21 $ .

In the third test case, $ a=4, b=6, l=48 $ . The possible values of $ k $ (and corresponding $ x,y $ ) are as follows:

- Choose $ k = 2, x = 1, y = 1 $ . Then $ k \cdot a^x \cdot b^y = 2 \cdot 4^1 \cdot 6^1 = 48 = l $ .
- Choose $ k = 3, x = 2, y = 0 $ . Then $ k \cdot a^x \cdot b^y = 3 \cdot 4^2 \cdot 6^0 = 48 = l $ .
- Choose $ k = 8, x = 0, y = 1 $ . Then $ k \cdot a^x \cdot b^y = 8 \cdot 4^0 \cdot 6^1 = 48 = l $ .
- Choose $ k = 12, x = 1, y = 0 $ . Then $ k \cdot a^x \cdot b^y = 12 \cdot 4^1 \cdot 6^0 = 48 = l $ .
- Choose $ k = 48, x = 0, y = 0 $ . Then $ k \cdot a^x \cdot b^y = 48 \cdot 4^0 \cdot 6^0 = 48 = l $ .

思路

这道题 a 和 b 都很小,而 l 却很大。

所以枚举 x 和 y,计算 k 就可以了。

参考代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;

//const int N = ;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin>>t;
	
	while(t--)
	{
		set <ll> ans;
		ll a, b, l;
		
		cin>>a>>b>>l;
		
		for(ll i = 1, a_x = 1; a_x <= l; i++, a_x *= a)
		{
			for(ll j = 1, b_y = 1; b_y <= l; j++, b_y *= b)
			{
				ll k = l / (a_x * b_y);
				
				if(k * a_x * b_y == l)
					ans.insert(k);
			}	
		}
		
		cout<<ans.size()<<"\n";
	}
	
	return 0;
}

原题链接:CF1933C Turtle Fingers: Count the Values of k


喜欢文章的可以点个关注+收藏,或者顺手一个小心心也可以,最近刷题较多,博文发的很频繁,制作不易,不喜勿喷(全文约 3.4K 字不值得你你的关注吗?)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/554966.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何用ChatGPT进行论文撰写?

原文链接&#xff1a;如何用ChatGPT进行论文撰写&#xff1f;https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247601619&idx1&snb686fbe87dedfac2df3a6afe780b2ffe&chksmfa820c34cdf5852251dca64597024ea62ddbde280086535ec251f4b62b848d9f9234688384e6…

【论文速读】| 大语言模型是边缘情况模糊测试器:通过FuzzGPT测试深度学习库

本次分享论文为&#xff1a;Large Language Models are Edge-Case Fuzzers: Testing Deep Learning Libraries via FuzzGPT 基本信息 原文作者&#xff1a;Yinlin Deng, Chunqiu Steven Xia, Chenyuan Yang, Shizhuo Dylan Zhang, Shujing Yang, Lingming Zhang 作者单位&…

js高级 笔记02

目录 01 object提供的一些静态方法 02 词法作用域 03 作用域链 04 arguments的使用 05 开启严格模式 06 高阶函数 07 闭包 01 object提供的一些静态方法 Object.create() 对象继承 Object.assign(对象1,对象2) 对象合并 可以将对象2 里面的可枚举属性和自身的属性合并到…

C语言简单的数据结构:单链表的有关算法题(2)

题目&#xff1a; 4. 单链表相关经典算法OJ题3&#xff1a;合并两个有序链表5. 循环链表经典应⽤-环形链表的约瑟夫问题6. 单链表相关经典算法OJ题5&#xff1a;分割链表 接着我们介绍后面的三道题&#xff0c;虽然代码变多了但我们的思路更加通顺了 4. 单链表相关经典算法OJ题…

前端请求404,后端保无此方法

1、微信小程序前端路径404 2、后端报无此路径 3、查看路径下对应的方法 发现忘了在list方法前加GetMapping(“/list”)&#xff0c;加上即可

Python用于创建和可视化环形图的工具库之pycirclize使用详解

概要 Python pycirclize库是一个用于创建和可视化环形图的工具,它提供了丰富的特性和功能,可以帮助用户展示环形结构数据的关系和比例。本文将深入探讨pycirclize库的安装、特性、基本功能、高级功能、实际应用场景等方面。 安装 安装pycirclize库非常简单,可以通过pip命令…

2024年华中杯数学建模竞赛全攻略:ABC题思路解析+代码实现+数据集+论文撰写+全程答疑

引言 &#xff08;比赛后所有题目资料在文末获取呀&#xff09; 华中杯数学建模竞赛是数学建模领域的一项重要赛事&#xff0c;它不仅考验参赛者的数学建模能力&#xff0c;还考验了编程技能、数据分析能力和论文撰写能力。为了帮助参赛者更好地准备2024年的竞赛&#xff0c;本…

记一次webshell排查但又无webshell的应急

某次应急中&#xff0c;客户吓坏了&#xff0c;说是内网流量分析设备中有很多webshell连接告警&#xff0c;作为一名卑微但又不失理想的安服仔&#xff0c;毅然直奔前线… 过程 去到现场后&#xff0c;直接打开客户的流量分析设备&#xff0c;的确看到一堆冒红的webshell连接…

【Java开发指南 | 第十二篇】Java循环结构

读者可订阅专栏&#xff1a;Java开发指南 |【CSDN秋说】 文章目录 循环1、while循环2、do-while循环3、for循环 break 关键字数组for循环continue 关键字 循环 与C语言相同&#xff0c;Java中有三种主要的循环结构&#xff1a; while 循环do…while 循环for 循环 1、while循…

python二级题目-仅使用 Python 基本语法,即不使用任何模块,编写 Python 程序计算下列数学表达式的结果并输出,小数点后保留 3 位。

x(((3**4)5*(6**7))/8)**0.5 .format 用法一&#xff1a; print({}.format(1)) 1 print(这个是format的用法{}。。。.format(3)) 这个是format的用法3 ’大括号1:{},大括号2:{},大括号3:{}‘.format(3,4,5) print(’大括号1:{},大括号2:{},大括号3:{}‘.form…

内业减少80%人工操作,林地地形轻松测!

林业作为维护生态平衡和保护环境的关键领域&#xff0c;其科学管理和合理利用是当前林业工作的重中之重。林业调查旨在全面了解当前林业资源的状况&#xff0c;其中林地地形测量是林业调查的基础工作。通过对林地地形的准确测量&#xff0c;可获取森林的地理位置、面积、地貌、…

(CVPR,2024)CAT-Seg:基于成本聚合的开放词汇语义分割

文章目录 摘要引言方法计算成本与嵌入空间成本聚合类别成本聚合CAT-Seg框架 实验 摘要 开放词汇的语义分割面临着根据各种文本描述对图像中的每个像素进行标记的挑战。在这项工作中&#xff0c;我们引入了一种新颖的基于成本的方法&#xff0c;以适应视觉语言基础模型&#xf…

设计模式———单例模式

单例也就是只能有一个实例&#xff0c;即只创建一个实例对象&#xff0c;不能有多个。 可能会疑惑&#xff0c;那我写代码的时候注意点&#xff0c;只new一次不就得了。理论上是可以的&#xff0c;但在实际中很难实现&#xff0c;因为你无法预料到后面是否会脑抽一下~~因此我们…

RocketMQ顺序消息消费重试DEMO

Producer - 加入了id为key&#xff0c;msg为bean的json字符 public class AddProducer {public static void main(String[] args) throws Exception {DefaultMQProducer producer new DefaultMQProducer("a-group");producer.setNamesrvAddr("192.168.0.211:9…

损失函数:Cross Entropy Loss (交叉熵损失函数)

损失函数&#xff1a;Cross Entropy Loss &#xff08;交叉熵损失函数&#xff09; 前言相关介绍Softmax函数代码实例 Cross Entropy Loss &#xff08;交叉熵损失函数&#xff09;Cross Entropy Loss与BCE loss区别代码实例 前言 由于本人水平有限&#xff0c;难免出现错漏&am…

密码学 | 椭圆曲线密码学 ECC 入门(二)

目录 4 椭圆曲线&#xff1a;更好的陷门函数 5 奇异的对称性 6 让我们变得奇特 ⚠️ 原文地址&#xff1a;A (Relatively Easy To Understand) Primer on Elliptic Curve Cryptography ⚠️ 写在前面&#xff1a;本文属搬运博客&#xff0c;自己留着学习。如果你和我一样…

【Linux】应用层协议:HTTP

URL 在之前的文章中我们实现了一个网络版本的计算器&#xff0c;在那个计算器中揉合了协议定制以及序列化反序列化的内容&#xff0c;我们当时也自己定制了一套协议标准&#xff0c;比如请求和响应的格式应该是什么&#xff1f;如何读到一个完整的报文&#xff1f;支持的运算符…

【XR806开发板试用】在 xr806 上移植 LVGL

本文参与极术社区的《基于安谋科技STAR-MC1的XR806开发板试用》活动。 不多废话&#xff0c;直接开搞&#xff0c;先上效果图 准备 开发环境啥的&#xff0c;已经有很多文章了&#xff0c;这里就不再提搭建开发环境的相关内容了。 一个屏幕(1.8’ 128x160) LVGL源码(v8.0.2…

京东微服务microApp使用总结

前言 基于现有业务门户进行微服务基础平台搭建 主应用框架&#xff1a;vue3vite 子应用框架&#xff1a;vue2webpack / vue3vite在这里插入代码片 本地调试即可&#xff1a;主应用子应用进行打通&#xff08;注意&#xff1a;两者都是vue3vite&#xff09; 问题总结 1.嵌入…

压缩感知的概述梳理(3)

参考文献 Adaptive embedding: A novel meaningful image encryption scheme based on parallel compressive sensing and slant transform 文献内容 梳理 列表形式 并行压缩感知核心元素与流程 信号 x 长度&#xff1a;N表示&#xff1a;(x \sum_{i1}^{N} a_i\psi_i \su…