edward_mj

【题目大意】
求G^(Sum(C(n,i))) % 999911659
其中i | n。
【算法分析】
我们来围观999911659这个数字。
首先他是一个素数。其次，它-1以后是一个square free number。
素数有什么性质呢？
那就是a^x = a^(x % phi(p)) (mod p)。其中p是素数。
然后phi(素数)=这个素数-1。
现在问题聚焦成求 Sum(C(n,i)) % 999911658。  其中 i | n
由于那个可爱的999911658是square free number，于是我们将他分解质因数。
发现只有4个素因子，分别是2、3、4679、35617
然后呢？
因为是分解质因数，所以它们都是素数（废话=.=）
我们单独对这4个素因子求Sum(C(n,i)) % p。
于是乎因为p是素数，所以我们来一个Lucas定理，就可以很方便的算出组合数。
当然，期间还要用到我以前说的“不知名定理”（实际上叫“欧拉定理”）。
（不知道的同学看这里：http://hi.baidu.com/edwardmj/blog/item/24c2e52c0133625c4fc2264a.html）
最后呢，我们得出4个同余方程：
X=A1 (mod 2)
X=A2 (mod 3)
X=A3 (mod 4679)
X=A4 (mod 35617)
好嘞，由于mod的都是素数，所以必然它们是两两互质的。
所以直接上中国剩余定理。
不知道的同学可以参照《算法艺术与信息学竞赛》 （黑书）的P231。
当然这里面涉及到的拓展欧几里得算法在黑书里也有，位于P219。
【其它】
这里面有个小技巧，就是由于算组合数时要用到那个阶乘，可以预处理出来。
由于使用了Lucas定理，所以每个阶乘都不会超过要mod的那个数字。
于是只用处理4个数组，它们的长度分别是2、3、4679、35617。
令人激动的是：1A。
更令人激动的是：
1 27533 edward_mj 632K 15MS G++ 2.04K 2010-06-02 21:14:09 2 27541 AekdyCoin 404K 30MS G++ 2.30K 2010-06-02 21:33:18 3 27538 AekdyCoin 456K 30MS G++ 2.78K 2010-06-02 21:27:11 4 27543 AekdyCoin 400K 45MS G++ 2.17K 2010-06-02 21:36:11 5 27546 AekdyCoin 396K 60MS G++ 2.14K 2010-06-02 21:41:21 6 26437 sonicmisora 412K 230MS G++ 1.92K 2010-05-28 10:56:15 7 26483 zxytim 384K 307MS G++ 2.50K 2010-05-28 14:05:33 8 26349 root 1344K 384MS G++ 2.67K 2010-05-27 20:19:52 9 27515 sevenk 348K 762MS G++ 3.55K 2010-06-02 20:48:10 10 26890 AekdyCoin 348K 777MS G++ 3.04K 2010-05-30 20:43:11 11 26886 AekdyCoin 352K 808MS G++ 2.90K 2010-05-30 20:32:14 12 26438 hyf042 844K 929MS G++ 2.69K 2010-05-28 11:05:21 13 26891 AekdyCoin 288K 933MS G++ 3.31K 2010-05-30 20:52:39 当然，师傅由于之前写疵，所以后面那堆是他在疵状态下写的。
前面的是在使用了那个小技巧之后的时间。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const int phi=999911658;
int mm=999911659;
const int N=200000;
struct zys{int L[N],Num[N],t;}pz,nz;
int n,G;
lld a[N];
lld JC[5][37777];

void Div(zys &p,int x){
p.t=0;
for (int i=2;i*i<=x;i++)
if (x%i==0){
p.L[++p.t]=i;
p.Num[p.t]=0;
while (x%i==0){
p.Num[p.t]++;
x/=i;
}
}
if (x!=1) {p.L[++p.t]=x; p.Num[p.t]=1;}
}

void makejc(){
int i,j;
for (i=1;i<=4;i++){
JC[i][0]=1;
for (j=1;j<=pz.L[i];j++)
JC[i][j]=JC[i][j-1]*j%pz.L[i];
}
}

lld Pow_mod(lld x,lld cf,int &mod){
if (cf==0) return 1;
lld res=Pow_mod(x,cf/2,mod);
res=res*res%mod;
if (cf%2) res=res*x%mod;
return res;
}

lld Normal_C(int m,int n,int i){
int p=pz.L[i];
return JC[i][m]*Pow_mod(JC[i][n]*JC[i][m-n]%p,p-2,p)%p;
}

lld C(int m,int n,int i){
if (!n) return 1;
int p=pz.L[i];
if (m%p return Normal_C(m%p,n%p,i)*C(m/p,n/p,i)%p;
}

void deal(int sum){
for (int i=1;i<=4;i++)
a[i]=(a[i]+C(n,sum,i))%pz.L[i];
}

void dfs(int dep,int sum){
if (dep>nz.t){
deal(sum);
return;
}
dfs(dep+1,sum);
for (int i=1;i<=nz.Num[dep];i++){
sum*=nz.L[dep];
dfs(dep+1,sum);
}
}

lld exgcd(lld a,lld b,lld &x,lld &y){
if (!b){
x=1; y=0;
return a;
}
lld res=exgcd(b,a%b,x,y),t;
t=x;
x=y;
y=t-a/b*y;
}

void solve(){
lld i,j,Mi,ans=0,p,q,M=phi;
for (i=1;i<=4;i++){
Mi=M/pz.L[i];
exgcd(Mi,pz.L[i],p,q);
ans=(ans+Mi*p*a[i])%M;
}
if (ans<0) ans+=M;
cout << Pow_mod(G,ans,mm) << "n";
}

int main(){
cin >> n >> G;
G%=mm;
if (G==0) {printf("0n"); return 0;}
Div(pz,phi);
Div(nz,n);
makejc();
dfs(1,1);
solve();
return 0;
}

【题目大意】
求C(n+m,n) % p的值。
保证p是素数。
【算法分析】
师傅说存在一个叫Lucas定理。
他在维基百科上：http://en.wikipedia.org/wiki/Lucas%27_theorem
除了这个Lucas定理以外，还要用到快速幂和另外一个不知名定理：
若b与p互质，则(a/b) = a * b^(p-2) (mod p)。
【其它】算阶乘的时候弄错几次，要开int64，不然会乘到溢出的。
【CODE】
#include #include #include #include using namespace std;
typedef __int64 lld;
lld p;
lld jc[105555];

void init(){
jc[0]=1;
for (lld i=1;i<=p;i++) jc[i]=jc[i-1]*i%p;
}

lld Pow_mod(lld x,lld cf){
if (cf==0) return 1;
lld res=Pow_mod(x,cf/2);
res=res*res%p;
if (cf%2) res=res*x%p;
return res;
}

lld C(lld m,lld n){
if (n>m) return 0;
return jc[m]*Pow_mod(jc[n]*jc[m-n]%p,p-2)%p;
}

lld solve(lld m,lld n){
if (n==0) return 1;
return C(m%p,n%p)*solve(m/p,n/p)%p;
}

int main(){
lld Tc,i,m,n;
cin >> Tc;
for (i=0;i cin >> n >> m >> p;
init();
cout << solve(m+n,n) << "n";
}
return 0;
}

【题目】
求A^B % C
A,C<=1e9。
B<=10^1000000
【算法分析】
师傅说有一个公式
A^x=A^(x % phi(c) + phi(c) )    (mod c)
然后直接套。
【其它】1A
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
const lld N=1005555;
lld A,B,C,phi;
char str[N];

void makephi(){
lld x=C,i;
phi=C;
for (i=2;i*i<=x;i++)
if (x%i==0){
phi=phi/i*(i-1);
while (x%i==0) x/=i;
}
if (x!=1) phi=phi/x*(x-1);
}

void String_to_Number(){
bool flag=false;
lld i,j,Len=strlen(str+1);
B=0;
for (i=1;i<=Len;i++){
B=B*10+str[i]-‘0’;
if (B>=phi){
flag=true;
B%=phi;
}
}
if (flag) B+=phi;
}

lld Pow_mod(lld x,lld cf){
if (!cf) return 1;
lld res=Pow_mod(x,cf/2);
res*=res; res%=C;
if (cf%2) res*=x;
res%=C;
return res;
}

int main(){
while (scanf("%I64d %s %I64d",&A,str+1,&C)!=EOF){
makephi();
String_to_Number();
printf("%I64dn",Pow_mod(A,B));
}
return 0;
}

【题目大意】
求LCM(1,N)+LCM(2,N)+LCM(3,N)+…+LCM(N,N)
【算法分析】
ans=n*(1/gcd(1,n)+2/gcd(2,n)+…+n/gcd(n,n))
其中显然gcd(x,n)都是n的约数。
然后我们都知道n的约数的个数是n^0.5级别的。
于是可以考虑把分母相同的合并。
然后设x为n的一个约数，那么(kx,n)=x 当且仅当满足 (k,n/x)=1
然后再有不等式kx<=n 即 k<=n/x。
然后。。。
k<=n/x   (k,n/x)=1     想到了什么？
欧拉函数~
设t=n/x
但是现在要求的是所有满足  (k<=t)&& (k,t)=1  的k的和。
然后我们来证一个性质。
那个和=t*phi(t)/2。

假设：gcd(x,t)=g && g>1
那么gcd(t-x,t)%g=0
为什么？
∵t%g=0   x%g=0  ∴ (t-x) % g=0。
所以可以利用反证法得出，假如(x,t)=1那么 (t-x,t)=1
于是互质的数都是成对的，且他们的和是t。
所以总体来说可以分成phi(t)/2组，每组的和为t，所以总和为t*phi(t)/2。

但是如果t为偶数的话，有可能出现t/2算两次的情况之类。
但是显然，t为偶数时，t/2和t不互质，不会算进欧拉函数里，所以不用考虑。

然后最后的做法是：
1、
用筛法把1e6的素数和欧拉函数都筛出来。 这一步的时间复杂度是O(1e6 lg 1e6)。
这个时间复杂度可能很多人会说= =，但是至少我在网上看到的筛法好像都是O(n lg n)的复杂度的。
虽然他们叫线性筛，我也一直认为是线性的，直到APIO听了CDQ讲课，其中有一个典型的复杂度分析就是我这种写法的筛。最后的结论是O(n lg n)。。。
2、
先求n的所有约数，然后利用上面的性质求和。
但是这题异常猥琐，时间非常紧，要先用筛出的素数对n分解质因数，然后再DFS求约数。
一开始我过于信任SPOJ的机子，直接一个for过去求约数，复杂度O(n^0.5)。
然后除了极限数据，我自己的机子卡着5s过。但是上面就不行了。

用了分解质因数以后，就由于那些素数的小步伐跳跃，卡过了。。。~

【时间复杂度】
O(1e6 lg 1e6+ ( T(n^0.5) + lg n )*TestCaseNum)。
其中T(x)函数表示<=x的数里的素数个数。
然后第二步如果是我本来那种直接暴力找约数的话，那么复杂度就是
O(1e6 lg 1e6+ ( n^0.5 + lg n)*TestCaseNum)。
最终，由于TestCaseNum把常数无限放大，我的暴力悲剧地TLE了。。。
【其它】
在HWG的博客看到这题。。。于是做了一下，没想到被常数卡成SB了。。。
Orz，一开始以为A|B是AB互质的意思，现在已经修正。。。
【CODE】
#include #include #include typedef long long lld;
const int N=1000001;
int n,Tc,pt,Lt,sum;
bool prime[N];
int phi[N],pl[N],L[N],Num[N];
lld ans;
char ss[200];

void init(){
memset(prime,true,sizeof(prime));
pt=0;
int i,j;
for (i=1;i for (i=2;i for (pl[++pt]=i,j=i;j phi[j]=phi[j]/i*(i-1);
prime[j]=false;
}
}

void Div(int x){
Lt=0;
for (int i=1;(pl[i]*pl[i]<=n) && (x!=1);i++){
if (x%pl[i]==0) {L[++Lt]=pl[i]; Num[Lt]=0;} else continue;
while (x%pl[i]==0){
Num[Lt]++;
x/=pl[i];
}
}
}

void dfs(int dep){
if (dep>Lt){
ans+=((lld)(phi[sum])*sum)>>1;
if (sum*sum!=n) ans+=((lld)(phi[n/sum])*(n/sum))>>1;
return;
}
int tmp=sum;
dfs(dep+1);
for (int i=1;i<=Num[dep];i++){
sum*=L[dep];
if (sum>n/sum) break;
dfs(dep+1);
}
sum=tmp;
}

void Write(){
int tt=0;
while (ans){
ss[tt++]=ans%10+’0′;
ans/=10;
}
for (int i=tt-1;i>=0;i–) putchar(ss[i]);
putchar(‘n’);
}

void solve(){
phi[1]=2;
sum=1;
ans=0;
Div(n);
dfs(1);
ans*=n;
printf("%lldn",ans);
}

void Read(int &x){
char ch;
for (ch=getchar();!(ch>=’0′ && ch<='9');ch=getchar());
x=0;
for (;ch>=’0′ && ch<='9';ch=getchar())
x=x*10+ch-‘0’;
}

int main(){
init();
Read(Tc);
int i;
for (i=1;i<=Tc;i++){
Read(n);
solve();
}
return 0;
}