擴展歐幾裡得 求逆元（只要a與b互素，那麼就有逆元）
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define mod 9973
typedef long long ll;
void ExGcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return ;
}
ExGcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
int main(){
int t,T,rev,x;
int a,b;
scanf("%d",&T);
for(t=1;t<=T;t++){
scanf("%d %d",&a,&b);
ExGcd(b,mod,rev,x);
printf("%d\n",((rev*a)%mod+mod)%mod);
}
}
O(n)打素數表
[cpp]
int pn = 0,prime[MAXN],factor[MAXN];//factor[i]為i的最小素約數
void get_prime(int n){
int i,j;
for(i=1;i<=n;i++)
factor[i]=i;
for(i=2;i<=n;i++){
if(i==factor[i])prime[pn++]=i;
for(j=0;j<pn && prime[j]*i<=n;j++){
factor[i*prime[j]]=prime[j];
if(i%prime[j]==0)
break;
}
}
}
POJ 1845 二分（1+x+x^2...+x^n）求和
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define mod 9901
typedef long long ll;
const int MAXN=10000;
int a,b,k;
int p[MAXN],n[MAXN];
ll quick(ll num,ll mi){
ll ans=1;
while(mi){
if(mi%2)ans=(ans*num)%mod;
num=(num*num)%mod;
mi/=2;
}
return ans%mod;
}
ll sum(ll num,ll mi){
if(mi==0)return 1;
if(mi%2)
return (sum(num,mi/2)*(1+quick(num,mi/2+1)))%mod;
return (sum(num,mi/2-1)*(1+quick(num,mi/2+1))+quick(num,mi/2))%mod;
}
void factor(int a){
int i;
k=0;
for(i=2;i*i<=a;){ //sqrt(n)的復雜度分解整數
if(a%i==0){
p[k]=i;
n[k]=0;
while(a%i==0){
n[k]++;
a/=i;
}
k++;
}
if(i>2)i+=2;
else i++;
}
if(a>1){
p[k]=a;
n[k]=1;
k++;
}
}
int main(){
int i;
scanf("%d %d",&a,&b);
factor(a);
int ans=1;
for(i=0;i<k;i++)
ans=(ans*(sum(p[i],n[i]*b))%mod)%mod;
printf("%d\n",ans);
}
POJ 1845 逆元的方法
[cpp]
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define mod 9901
typedef long long ll;
const int MAXN=10000;
int a,b,k;
int p[MAXN],n[MAXN];
void ExGcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return ;
}
ExGcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
}
int reverse(int num){
int rev,x;
ExGcd(num,mod,rev,x);
return rev;
}
ll quick(ll num,ll mi){
ll ans=1;
while(mi){
if(mi%2)ans=(ans*num)%mod;
num=(num*num)%mod;
mi/=2;
}
return ans%mod;
}
ll sum(ll num,ll mi){
if(num%mod==1) //注意到這種情況不能用逆元，因為num-1與mod不互素
return (mi+1)%mod;
return (((quick(num,mi+1)-1+mod)%mod)*reverse((num-1)%mod)%mod+mod)%mod;
}
void factor(int a){
int i;
k=0;
for(i=2;i*i<=a;){ //sqrt(n)的復雜度分解整數
if(a%i==0){
p[k]=i;
n[k]=0;
while(a%i==0){
n[k]++;
a/=i;
}
k++;
}
if(i>2)i+=2;
else i++;
}
if(a>1){
p[k]=a;
n[k]=1;
k++;
}
}
int main(){
int i;
scanf("%d %d",&a,&b);
factor(a);
int ans=1;
for(i=0;i<k;i++)
ans=(ans*(sum(p[i],n[i]*b))%mod+mod)%mod;
printf("%d\n",ans);
}
SPOJ DIVSUM
[cpp]
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
const int MAXN = 1501000, N = 500010;
int pn = 0, prime[MAXN], factor[MAXN];
void get_prime(int n){
int i,j;
for(i=1;i<=n;i++)
factor[i]=i;
for(i=2;i<=n;i++){
if(i==factor[i])prime[pn++]=i;
for(j=0;j<pn && prime[j]*i<=n;j++){
factor[i*prime[j]]=prime[j];
if(i%prime[j]==0)
break;
}
}
}
int main()
{
int cases;
get_prime(N);
scanf("%d", &cases);
while(cases--)
{
int n, tmpn;
long long ans = 1;
scanf("%d", &n);
tmpn = n;
while (tmpn != factor[tmpn])
{
long long fac = factor[tmpn], mtp = fac;
while (tmpn % fac == 0)
{
mtp *= fac;
tmpn /= fac;
}
ans *= (1 - mtp) / (1 - fac);
}
if (tmpn > 1)
ans *= (1 + tmpn);
ans -= n;
printf("%lld\n", ans);
}
return 0;
}
SPOJ DIVSUM 另一種做法
[cpp]
#include<cstdio>
using namespace std;
int sum[500100];
int main()
{
int T,t,i,j,n;
scanf("%d",&T);
for(i=1;i<=500000;i++){
for(j=2;i*j<=500000;j++){//若j從1開始則會算上本身
sum[i*j]+=i;
}
}
for(t=1;t<=T;t++){
scanf("%d",&n);
printf("%d\n",sum[n]);
}
}
