E. Border是什么?拓展欧几里得+mod分析
Astronaut Natasha arrived on Mars. She knows that the Martians are very poor aliens. To ensure a better life for the Mars citizens, their emperor decided to take tax from every tourist who visited the planet. Natasha is the inhabitant of Earth, therefore she had to pay the tax to enter the territory of Mars.
There are n
(资料图)
banknote denominations on Mars: the value of i-th banknote is ai
. Natasha has an infinite number of banknotes of each denomination.
Martians have k
fingers on their hands, so they use a number system with base k. In addition, the Martians consider the digit d (in the number system with base k) divine. Thus, if the last digit in Natasha"s tax amount written in the number system with the base k is d
, the Martians will be happy. Unfortunately, Natasha does not know the Martians" divine digit yet.
Determine for which values d
Natasha can make the Martians happy.
Natasha can use only her banknotes. Martians don"t give her change.
Input
The first line contains two integers n
and k (1≤n≤100000, 2≤k≤100000
) — the number of denominations of banknotes and the base of the number system on Mars.
The second line contains n
integers a1,a2,…,an (1≤ai≤109
) — denominations of banknotes on Mars.
All numbers are given in decimal notation.
Output
On the first line output the number of values d
for which Natasha can make the Martians happy.
In the second line, output all these values in increasing order.
Print all numbers in decimal notation.
Examples
Input
Copy
2 812 20
Output
Copy
20 4
Input
Copy
3 1010 20 30
Output
Copy
10
Note
Consider the first test case. It uses the octal number system.
If you take one banknote with the value of 12
, you will get 148 in octal system. The last digit is 48
.
If you take one banknote with the value of 12
and one banknote with the value of 20, the total value will be 32. In the octal system, it is 408. The last digit is 08
.
If you take two banknotes with the value of 20
, the total value will be 40, this is 508 in the octal system. The last digit is 08
.
No other digits other than 08
and 48 can be obtained. Digits 08 and 48
could also be obtained in other ways.
The second test case uses the decimal number system. The nominals of all banknotes end with zero, so Natasha can give the Martians only the amount whose decimal notation also ends with zero.
#includeusing namespace std;typedef long long ll;#define rep(i,a,b) for(int i=a;i=a;i--)set st;ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b);}/*相似题:蓝桥杯,包子凑数核心思想:a1*x1+a2*x2+...+an*xn==gcd(a1,a2,...,an)*? <---原理:拓展欧几里得也就是他们能凑出来的树肯定是,gcd的倍数,然后在mod系下的话,只要枚举到mod就好了当时只想着把他们都转化成mod系下的数字,然后在进行计算,事实就是这样会更麻烦*/int main(){ int n,m; scanf("%d %d",&n,&m); ll val,G; rep(i,1,n+1){ scanf("%lld",&val); if(i==1)G=val; else G=gcd(G,val); } for(ll i=0,j=0;j<=m;j++,i+=G){ st.insert(i%m); } printf("%d\n",st.size()); set::iterator it; for(it=st.begin();it!=st.end();it++){ printf("%lld%c",*it,it==st.end()?"\n":" "); } return 0;}
标签: 欧几里得
相关推荐:
最新新闻:
- E. Border是什么?拓展欧几里得+mod分析
- 520还在画玫瑰?教你用MATLAB画个玫瑰花球|实时焦点
- 神谷英树将《猎天使魔女:起源》比作童心绘本-全球播报
- IPO大潮退去,美股繁盛时期上市的大批股票现在面临退市风险
- 《碟中谍7》官方幕后花絮:阿汤哥太拼 3000米飞车跳崖|全球快播报
- 苹果新一代显示器来了:屏幕升级为mini LED
- 卡梅隆封神往事:一个天才疯子和《阿凡达》的20年_世界实时
- Steam喜加一:圣诞主题像素排球游戏《Jollyball》
- NVIDIA CES新品发布会官宣:RTX 4070 Ti、RTX 40笔记本显卡要来了:热门看点
- 热门看点:币安将以10.22亿美元的价格收购加密货币借贷平台Voyager的资产
- 环球快消息!ZOL科技早餐:骁龙8 Gen2新机2999元,魅族19外观将揭晓
- 联想USB 3.0扩展坞29元限时秒:4个USB接口 支持Type-C供电-世界热点
- 性价比还得看AMD 6核锐龙+显卡+主板套装1239元:当前要闻
- 《水浒风云传》确定12月22日登陆Xbox和Switch 天天观速讯
- 【天天新视野】《原神》剧情视频「秋津羽戏」讲述人与妖的友情
- 高手用虚幻5做出《刺客信条》粉丝最期待的游戏功能
- 三强联手:Steam与苹果正式加盟特斯拉_天天短讯
- 马斯克狂卖特斯拉股票:三天套现250+亿人民币
- 环球时讯:CES 2023 多家电脑厂商预热新款大屏游戏本
- 96核心192线程!AMD Zen4线程撕裂者7000将至 当前速递
- 冬日特别福利!即刻上手领取你的穿越火线限定礼包吧:今日热讯
- 姆巴佩决赛失利首度发声:我们会回来的! 每日观点
- 【世界独家】艰难的阿根廷,比梅西更需要这座大力神杯
- ARPG《致命躯壳:完整版》推出Switch版|当前视讯
- Epic喜加一:《小马格斗》免费领取
- 美国国防部:没有任何证据显示UFO与外星人有关 今日讯
- Epic Games支付5.2亿美元以解决侵犯儿童隐私问题
- 《模拟人生4》玩家合计游戏时长达14亿小时_环球讯息
- 【天天热闻】《装甲核心6:境界天火》不会包含战役合作模式
- 【爆料】英特尔 i5-13400 评测流出:6 大核 4 小核,性能接近 i5-12600K
- 每日讯息!旺旺因虚假广告被罚:宣传称富含蛋白质实际不达标
- 这一百多年前的病,喜来乐也治不好|环球实时
- 世界看热讯:《巫师3》PC版热修复补丁已发布 提高稳定性和性能
- IGN评选游戏史上销量最高TOP10 《大镖客2》第十_环球观热点
- 手工耿自制多功能硬核鱼竿:外形似大狙 还能放风筝 天天时讯
- 为何小米 13 Pro 不是直屏?雷军解释:做成直屏会太厚
- 《英雄传说:创之轨迹》明年7月7日登陆欧美 新预告公开:动态
- 【新品】ROG 发布白色版 RTX 4090 / 4080 猛禽显卡
- 小米年底裁员?内部人士:确有其事 规模不大、补偿政策为N+2
- 业界人士分析《宝可梦》动画换主角:功成身退顺其自然
- 这个由AI生成的《黑暗之魂》电影版让我们眼前一亮
- 《阿凡达2:水之道》M站用户评分7.1:特效很棒 剧情稀烂
- SE手游新作《王国之心 Missing-Link》明年1月开启测试 新视觉图释出|世界消息
- 《FIFA 23》登顶2022年英国圣诞节零售榜
- 百事通!曾客串《复联4》的《阿凡达2》小演员谈卡梅隆:他像父亲一样
- 《巫师3》Steam 24小时在线峰值接近9万|焦点速看
- 57.5%赞成!马斯克或将卸任Twitter CEO
- 索尼《蜘蛛侠》宇宙将拍反派催眠骗子
- 疫苗巨头打起了mRNA专利争夺战:环球热消息
- 天天热文:小岛工作室1:1 Ludens雕塑落成 官方发布幕后视频
- 满功耗GeForce RTX 3060护航 华硕天选3锐龙版游戏表现更上一层楼
- 全球观天下!网传小米年底大裁6000人 内部人士出面辟谣
- “家居生态联盟”发起成立,容声构建家居美学新生态_今热点
- 性能强悍大内存是基础!这三款千元机闭眼入_每日视点
- 2022年,最能打的工业元宇宙企业都有谁?工业元宇宙排行TOP50发布_环球今日讯
- 克里斯蒂安·贝尔:不介意以其他角色身份重回MCU_环球聚看点
- 阿根廷队三星冠军T恤5秒售罄 多次紧急补货均被抢光-聚焦
- 连锁面馆为什么没有开出“中国肯德基”?
- 焦点讯息:好评如潮《战神4》新史低167元|《影子战术》仅1折
- 玩家用Mod重做《魔兽3重制版》 实现最初预告片效果
- 每日速读!桥本环奈主演《黑色夜晚大游行》电影新剧照 12月23日上映
- Win11桌面化身“白板” 允许用户自行绘制桌面贴纸
- 你达标了吗?我国成年人均纸质书阅读4.76本 仅小学生的1/3
- AMD RX7900被吐槽空气卡:用户重回N卡阵营!真香 环球短讯
- 2022游戏安全行业峰会成功举办!《2022游戏安全白皮书》发布
- 今日观点!添可芙万Steam2.0专治重油重污 140℃高温蒸汽直喷地面
- 荣耀80 GT成三体动画官方指定产品 突破性能封锁
- UR机器人关键的6大系统技术解说
- 心系天下三星W23 | W23 Flip 格调之外 自有主张_观点
- 硅料降价后,HJT明年预期有何变化?丨见智研究
- “末代皇后”婉容悲惨的一生
- 《极品飞车22:不羁》明年一月迎来更新 扩展社交游戏功能
- 大罗祝贺梅西:巴西人都为你加油 梅西让人放下仇恨
- 努比亚Z50发布:搭载骁龙8Gen2 2999元起售!
- 天天微头条丨《海岛大亨6》等9款游戏 将于12月31日退出XGP