有什么做旅游攻略的网站好/网站统计分析平台
求一个数n的所有约数复杂度sqrt(n)，i从1枚举到sqrt(n)，如果n%i==0,那么i和n/i都是n的约数
扩展欧几里得 求逆元（只要a与b互素，那么就有逆元）
#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)打素数表
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;}}
}
O(nlogn)打素数表
void get_prime(){int n;int i,j;for(i=2;i<=sqrt(n)+1;i++){if(!yes[i])for(j=i*i;j<=n;j+=i)yes[j]=1;}
}
POJ 1845 二分（1+x+x^2...+x^n）求和
#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);
}
#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
#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 另一种做法
#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]);}
}