欧拉函数一般形式:
当 n 为素数时: phi(n) = n-1
当 n 为合数时: phi(n) = n∏(1-1/p) 其中(p为n的素数因子)
题目pku1091,要求我们求 x1..xn,m这样的序列的个数,其中xi(1<=i<=n), 使 gcd(x1, ..,xn,m)=1;
我们按欧拉函数的形式猜想如下方程:
当 n 为素数时: phi(m,n) = m^n-1
当 n 为合数时: phi(m,n) = m^n∏(1-1/p^n) 其中(p为n的素数因子)
不给出严格数学证明(不会-_-),上两式具体含义:
当 n为素数 phi(m,n) = m^n-1 显然成立
当 n 为合数时 可以假象有一个m进制n位的数,然后其中一位有m的约数p的概率为1/p, 则n位同时有p的约数的概率就为(1-1/p^n), 运用乘法原理,可以得式 phi(m,n) = m^n∏(1-1/p^n)
code:
#include <iostream>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef __int64 llong;
const llong MAXN = 110000;
llong tf[MAXN], su[MAXN], ns, num[MAXN], nn;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void init() {
llong i, j;
for (i=2; i<MAXN; i++) {
if (!tf[i]) {
su[ns++]=i;
for (j=i*i; j<MAXN; j+=i) tf[j]=1;
}
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
llong ppow(llong a, llong b) {
llong ret=a;
llong i;
for (i=1; i<b; i++) ret *= a;
return ret;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main() {
llong n, m, i, p;
llong ans=0;
init();
while (scanf("%I64d%I64d", &n, &m)!=EOF) {
p=m; nn=0; ans=0;
for (i=0; i<ns; i++) {
if (p%su[i]==0) {
while (p%su[i]==0) p/=su[i];
num[nn++]=su[i];
}
if (p==1) break;
}
if (!nn) {
ans = ppow(m,n)-1;
} else {
ans = ppow(m,n);
for (i=0; i<nn; i++) {
ans = ans/ppow(num[i],n)*(ppow(num[i],n)-1);
}
}
printf("%I64d\n", ans);
}
return 0;
}
posted @
2007-09-02 22:57 豪 阅读(2474) |
评论 (4) |
编辑 收藏
(1)定理:设x0,x1,x2,...是无穷实数列,xj>0,j>=1,那么,
(i)对任意的整数 n>= 1, r>=1有
<X0,...,Xn-1,Xn,...,Xn+r> = <X0,...,Xn-1,<Xn,...,Xn+r>>
= <X0,...,Xn-1,Xn+1/<Xn+1,...,Xn+r>>.
特别地有
<X0,...,Xn-1,Xn,Xn+1> = <X0,...,Xn-1,Xn+1/Xn+1>
注:用该定理可以求连分数的值
(2)对于连分数数数列 <X0,...Xn> 有递推关系:
Pn = XnPn-1+Pn-2;
Qn = XnQn-1+Qn-2;
定义: P-2 = 0; P-1 = 1; Q-2 = 1; Q-1 = 0;
所以: P0 = X0; Q0 = 1; P1 = X1X0+1; Q1 = X1;
特别地:当 Xi=1 时, {Pn}, {Qn}为Fbi数列
(3)pell方程: x^2+ny^2=+-1的解法:
若n是平方数,则无解, 否则:
先求出sqrt(n)的连分数序列<x0,x1..xn> 其中xn = 2*x0;
对于 x^2+ny^2=-1
若n为奇数,则 x=Pn-1, y=Qn-1; n为偶数时无解
对于 x^2+ny^2=1
若n为偶数,则 x=Pn-1, y=Qn-1; n为奇数时x=P2n-1, y=Q2n-1
注:以上说的解均为最小正解
posted @
2007-08-28 14:59 豪 阅读(1290) |
评论 (2) |
编辑 收藏
问题简单来说就是 a = ai (mod ni) 求未知数a,
以下小结略去证明, 只是对定理作了必要的解释, 要了解相关定理,可查阅数论资料.
中国余数定理:
设 n=n1*n2...nk, 其中因子两两互质.有: a-----(a1,a2,...,ak), 其中ai = a mod ni, 则 a和(a1,a2,...,ak)关系是一一对应的.就是说可以由 a求出(a1,a2,...,ak), 也可以由(a1,a2,...,ak)求出a
推论1:
对于 a=ai (mod ni) 的同余方程,有唯一解
下面说说由(a1, a2, ..., ak)求a的方法:
定义 mi = n1*n2*...nk / ni; ci = mi(mf mod ni); 其中 mi*mf mod ni = 1;
则 a = (a1*c1+a2*c2+...+ak*ck) (mod n) (注:由此等式可求a%n, 当n很大时)
中国剩余定理关键是mf的求法,如果理解了扩展欧几里得 ax+by=d, 就可以想到:
mi*mf mod ni = 1 => mi*mf+ni*y=1;
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
const int MAXN = 100;
int nn, a[MAXN], n[MAXN];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int egcd(int a, int b, int &x, int &y) {
int d;
if (b == 0) {
x = 1; y = 0;
return a;
} else {
d = egcd(b, a%b, y, x);
y -= a/b*x;
return d;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int lmes() {
int i, tm=1, mf, y, ret=0, m;
for (i=0; i<nn; i++) tm *= n[i];
for (i=0; i<nn; i++) {
m = tm/n[i];
egcd(m, n[i], mf, y);
ret += (a[i]*m*(mf%n[i]))%tm;
}
return (ret+tm)%tm;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main() {
a[0] = 4; a[1] = 5;
n[0] = 5; n[1] = 11;
nn = 2;
printf("%d\n", lmes());
return 0;
}
posted @
2007-08-27 16:46 豪 阅读(11567) |
评论 (2) |
编辑 收藏
对于扩展欧几里得主要部分说明:
1. d' = bx'+(a mod b)y', d' = gcd(b, a mod b);
设 d = gcd(a, b), 因为 d = d', 所以
d = d' = bx'+(a mod b)y' = bx' + (a-floor(a/b)*b)y' = ay'+b(x'-floor(a/b)y');
故有迭代:
x = y'; y = x'-floor(a/b)y';
对于解方程主要部分说明:
1.首先给出两个定理(证明请查看相关数论书):
A. 方程 ax = b (mod n) 有解, 当且仅当 gcd(a, n) | b;
B. 方程 ax = b (mod n) 有d个不同的解, 其中 d = gcd(a, n);
2.证明方程有一解是: x0 = x'(b/d) mod n;
由 a*x0 = a*x'(b/d) (mod n)
a*x0 = d (b/d) (mod n) (由于 ax' = d (mod n))
= b (mod n)
证明方程有d个解: xi = x0 + i*(n/d) (mod n);
由 a*xi (mod n) = a * (x0 + i*(n/d)) (mod n)
= (a*x0+a*i*(n/d)) (mod n)
= a * x0 (mod n) (由于 d | a)
= b
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int egcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1; y = 0;
return a;
} else {
int tx, ty, d;
d = egcd(b, a%b, tx, ty);
x = ty; y = tx-a/b*ty;
return d;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void mels(int a, int b, int n) {
int tx, ty, d, x0, i;
d = egcd(a, n, tx, ty);
if (b%d==0) {
x0 = ((tx*b/d)%n+n)%n;
for (i=0; i<d; i++) {
printf("%d ", (x0+i*n/d)%n);
}
} else {
printf("No solutions!");
}
printf("\n");
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main() {
mels(14, 30, 100);
return 0;
}
posted @
2007-08-27 11:14 豪 阅读(2162) |
评论 (2) |
编辑 收藏
好久没写了,主要是不知道写什么,发个刚写好的比较通用的堆吧,sigh~
http://www.cppblog.com/qywyh/articles/28653.html
posted @
2007-07-23 21:04 豪 阅读(367) |
评论 (0) |
编辑 收藏