作者存档：edward_mj

【题目大意】
求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;
}