质因数分解
const int maxn=10000; bool book[maxn+10]; int prim[maxn+10],pnum=0; void getprim() { memset(book,0,sizeof(book)); pnum=0; book[1]=book[0]=1; for(int i=2;i<=maxn;++i) { if(!book[i]) { prim[pnum++]=i; } for(int j=0;j<pnum && prim[j]<=maxn/i ;++j) { book[prim[j]*i]=1; if(i % prim[j]==0) break; } } } ll fact[105][2]; int fnum=0; int getfact(ll x) { fnum=0; ll temp=x; for(int i=0;prim[i]<=temp/prim[i];++i) { fact[fnum][1]=0; if(temp%prim[i]==0) { fact[fnum][0]=prim[i]; while(temp % prim[i]==0) { fact[fnum][1]++; temp /=prim[i]; } fnum++; } } if(temp!=1) { fact[fnum][0]=temp; fact[fnum++][1]=1; } return fnum; } 等比数列求和（从1开始） ll sum(ll p ,ll n,ll mod) { if(p==0) return 0; if(n==0) return 1; if(n&1) return ( ( 1+powermod(p,n/2+1,mod) )%mod * sum(p,n/2,mod)%mod )%mod; else return ( (1+powermod(p,n/2+1,mod)) %mod *sum(p,n/2-1,mod)+powermod(p,n/2,mod)%mod)%mod; }
