不同余数的个数

cn8888

\[{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

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

kastin

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

下面我写了一个matlab函数powmod，用于计算幂模运算，算法效率比较高

1. function x=powermod(n,p,m)
   
2. % Montgomery快速幂模算法 x = n^p (mod m)
   
3. r = mod(n,m);  
   
4. tmp = 1;  
   
5. while p>1
   
6.     if rem(p,2)==1,tmp = mod(tmp*r,m); end
   
7.     r = mod(r*r,m);
   
8.     p =bitshift(p,-1);
   
9. end
   
10. 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

东论那边有回复，先转回来
http://bbs.cnool.net/cthread-105405736.html