Codeforces #499 E Border ( 裴蜀定理 )
2024-09-03 09:36:57
题意 : 给出 N 种纸币、并且给出面值、每种纸币的数量可以任选、问你得出来的数在 k 进制下、末尾位的数有多少种可能、输出具体方案
分析 :
纸币任意选择组成的和
可以用一个一次多项式来表示
A1*B1 + A2*B2 + A3*B3 + ... + An*Bn ( A 为面值、B 为数量 )
根据裴蜀定理、这个一次多项式的结果集应当是 gcd( A1、A2 .... An ) 的倍数
然后考虑怎么得到每个数 k 进制下的最后一位数
实际上你考虑一下十进制是怎么转化为 k 进制的
就能够分析出、只要将这个十进制模以 k 就能得到
那么也就是说要求 ( A1*B1 + A2*B2 + A3*B3 + ... + An*Bn ) % k 的结果集
模可以转化为减法 故有 A1*B1 + A2*B2 + A3*B3 + ... + An*Bn - y*k
那么结果集就应当是 gcd( A1、A2 .... An 、k ) 的倍数
那么总数就有 k / gcd( A1、A2 .... An 、k )
具体的方案就直接枚举 gcd 的倍数就行了、上界为 k
#include<bits/stdc++.h> using namespace std; int main(void) { int n, k; cin>>n>>k; ; ; i<=n; i++){ int tmp; cin>>tmp; ) GCD = tmp; else GCD = __gcd(GCD, tmp); } GCD = __gcd(GCD, k); cout<< k / GCD <<endl; ; i<k; i+=GCD) cout<<i<<" "; cout<<endl; ; }
最新文章
- 从零开始学 Java - Windows 下安装 Eclipse
- android学习链接
- CSS 框模型( Box module )
- LightOJ1051 Good or Bad(DP)
- 一些 Shell 脚本(持续更新)
- PureMVC(JS版)源码解析(二):Notification类
- 【Linux】常用命令
- Android 屏幕适配方案
- Mac OS X用户,使用homebrew安装,FreeBSD也可以
- 12-JSP&;EL&;JSTL
- MySQL 存储过程返回多个值
- 信号量(Semaphore)
- C#实现录音录像录屏源码
- Android典型界面设计(6)——ActionBar Tab+ViewPager+Fagment实现滑动导航
- C#程序解读
- 不知道哪里alert undefined 用下面的语句是js报错.F12能提示报错的地方window.alert=function(aa){ if (typeof (aa)";undefined";){ throw ";就是这";;}};
- HTC Vive前置摄像头API(未测试)
- redis配置密码认证,通过密码可以进行连接
- quartz定时任务时间表达式说明
- C# Console类的方法使用总结
热门文章
- 手把手教你用 Strace 诊断问题
- mweb发布文章为什么默认TinyMCE编辑器?
- 生成ini文件
- idea-代码格式化快捷键设置(2019.1版)
- linux centos 安装mongoDB
- 设置队列中文件上的“X”号的点击事件+uploadLimit动态加1
- oa_mvc_easyui_后台布局(3)
- [转载]十六进制数的两种不同表示:0x和H
- 如何在万亿级别规模的数据量上使用Spark
- javaScript中 数组的新方法(reduce)