C_liar
疑似NOJ数据有误 
快速幂模板，注意到2^63取等，所以必开ull. 
原因已经解释得很清楚了，并且我记得我曾因为爆ull却没写龟速乘WA过。 
注释内是测试数据，那么有： 
所以答案为： 
结果也确实是这样： 
样例也是必过的。 
还是WA. 
然后上面的这东西， 
😰多可怕啊，告诉你1000亿的平方除以10，余数得8的这堆东西，AC了。 
所以合理猜想，出题人没考虑到爆ull这事，所以有自然溢出的代码得以通过，而未自然溢出的代码不能通过。 
我看到数据范围，直接O(T)容斥，也开了long long，就是过不了，结果告诉我只用 int，O(NT) 的 for 循环就可以过掉吗？ 
比较难绷的是上面的代码过不了，下面的代码能过。 
所以n＞95935处的 if 判断完全是我有意为之。
本文略长，若有可能，请逐行耐心看完。
本人24小登，第一次发文，先叠甲。
高二打过OI，CCF6级，洛谷杀紫200+，C/C++码量估计万行级别。
平时摆，不太做NOJ，今晚稍微做了一下，发现有两道题比较...卡手。
这里是某一道题的题目描述。
同时注意到，快速幂过程中，可能出现两个数相乘爆掉ull的情况。
所以，我自然是使用龟速乘 (下文的mul函数) 代替了直接相乘，能够证明，mul函数不可能爆ull。
然后交了。
结果WA.
很疑惑。
回想起之前教过一个同学，当时直接用的快速幂，虽然我也意识到会爆ull的问题，但还是想让那位同学WA了之后再思考原因，就没有提醒。
但ta后来也没问我。
莫非...不用龟速乘？
于是考虑把mul()给换成原来的。
内心os：怎么可能不用龟速乘？难道两个2^63级别的数相乘没问题？莫非数据规模不够大？那我的代码怎么可能WA？
😰
然后交了一份这样的：
反复尝试后发现可能是必须要故意无符号整型溢出的，可能是我一开始想太多。
😨
又把输出 power(a%c,b,c) 中 %c 去掉。
输入 100000000000 2 10，得 8
不 是 ，这 也 能 A C 了 ？！
san值狂掉（
关于为什么输出8的解释：
至于 hack 数据，只要超过10^12左右，随机就能造出一堆来，根本不用手动构造。
😖所以究竟是我的想法有问题还是出题人数据造错了？？？
大家如果有感兴趣的，可以给你的AC程序试一试这组数据，查看结果是否正确。
各位如果发现我的代码确实有问题，也欢迎在评论区指正，不玻璃心谢谢🙏
另外类似的还有这题：
？虽然只是新手题，但好歹需要严谨一些吧，如果不行，数据范围就不要开那么大，OI中的数据基本都会触碰到上界的。
而这里用 int 能过，O(1) long long 过不掉的原因，大概又是令人讨厌的溢出问题吧。
简单计算了一下，确定了溢出范围：
所以是否标程中同样使用 int，又同样出现溢出问题？
再次叠甲：我的等差数列求和代码（开 long long）已经和网上找到的能AC的代码对拍过，在 n≤65535 范围下完全没问题。并且在提交时已用 assert 验证程序确实会进入 else 分支。
所以希望有大佬和我探讨一下究竟是确实如此，还是我的代码中存在错误🥹
另外如果有同学感兴趣，也可以和我讨论讨论这背后的社会现象☺
？怎么都到早上6点了（逃
- 下载图片
- 复制图片
2024-09-29
浏览1313
翱翔峰会（学习论坛）
登录后评论
14
5
9