cn8888 发表于 2014-9-9 13:14:27

\[{x^m}(\bmod {p^k}),\frac{{\varphi ({p^k})}}{{\gcd (\varphi ({p^k}),m)}} + \frac{{\varphi ({p^{k - m}})}}{{\gcd (\varphi ({p^{k - m}}),m)}} + \frac{{\varphi ({p^{k - 2m}})}}{{\gcd (\varphi ({p^{k - 2m}}),m)}} + \frac{{\varphi ({p^{k - 3m}})}}{{\gcd (\varphi ({p^{k - 3m}}),m)}} + ... + 1\]

还是猜测,不知道答案如何

cn8888 发表于 2014-9-9 15:34:17

m的值要先化简,使得小于等于p^k

kastin 发表于 2014-9-11 11:51:43

fungarwai 发表于 2014-9-9 10:52
除了这样做以外还有什么方法可以让matlab算对吗？

下面我写了一个matlab函数powmod，用于计算幂模运算，算法效率比较高
function x=powermod(n,p,m)
% Montgomery快速幂模算法 x = n^p (mod m)
r = mod(n,m);
tmp = 1;
while p>1
    if rem(p,2)==1,tmp = mod(tmp*r,m); end
    r = mod(r*r,m);
    p =bitshift(p,-1);
end
x=mod(r*tmp,m);
然后输入
r=zeros(2013,1);
for k=1:2013, r(k)=powermod(k,2013,2013); end
length(unique(r))
结果返回 693

fungarwai 发表于 2014-9-11 13:48:24

东论那边有回复，先转回来
http://bbs.cnool.net/cthread-105405736.html
页: 1 [2]
查看完整版本: 不同余数的个数