PTT
Submit
Submit
选择语言
正體中文
简体中文
PTT
Prob_Solve
[问题] TIOJ 1324
楼主:
vincent97198
(萌新冒险者)
2020-02-05 18:36:10
问题来源:https://tioj.ck.tp.edu.tw/problems/1324
问题:
底数与要除的数不互质时 a^k (mod n) = a^(k+phi(n)) (mod n)还成立吗?
还是我搞错解题方向了?
已有的想法:
用欧拉定理化简掉超大的指数
我的程式码(只拿了32分)
https://ideone.com/gYneXP
作者:
alan23273850
2020-02-05 18:51:00
反例: a=2, k=0, n=4
作者:
LPH66
(-6.2598534e+18f)
2020-02-05 21:30:00
k > 0 应该就对了, 所以你不能直接 % phi(n)
作者:
alan23273850
2020-02-06 11:47:00
k=1 还是错啊,2^1 不同余于 2^(1+2) mod 4
楼主: vincent97198 (萌新冒险者)
2020-02-06 16:09:00
看来我的方法不可行请问要如何解决不互质的情况呢?
作者:
alan23273850
2020-02-06 18:09:00
总觉得这题是要用程式的方式找出循环节,不需要特别针对互质&不互质作讨论像 4^k = 4 (mod 6) for all k,这个事实不跑跑看怎么会知道呢?
楼主: vincent97198 (萌新冒险者)
2020-02-06 22:42:00
谢谢alan大 我再想看看
作者:
oToToT
(å±å©)
2020-02-07 13:20:00
或许你可以查查扩展欧拉定理,虽然这应该不是正确的学术名词,不过满多中国选手会用的w
继续阅读
Re: [问题] 关于扩展欧几里得算法
LPH66
[问题] 关于扩展欧几里得算法
nevikw39
[问题] 机率的问题
bagafuok
[问题] 01背包的暴搜有什么特别的剪枝吗?
s89162504
[问题] Leetcode 294 Flip Game II
wheels
Fw: [问题] 使用bit来筛检质数
wa007123456
[问题] Knapsack problem
cloud2000s
[问题] 算法问题
cloud2000s
[问题] APCS 20191026 P4
fatcat8127
[问题] 高中数学请问
wozmirror
Links
booklink
Contact Us: admin [ a t ] ucptt.com