1.1~n的全部数的最小公倍数：lightoj 1289 传送门
分析：素因子分解可知这个数等于小于1~n的全部素数的最高次幂的乘积
预处理1~n的全部质数，空间较大，筛选的时候用位图来压缩。和1~n全部
质数的乘积，剩下的就是找最高次幂的问题了。
代码例如以下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define DWN(i,h,l) for(int i=(h);i>=(l);--i)
#define IFOR(i,h,l,v) for(int i=(h);i<=(l);i+=(v))
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))
#define PI acos(-1.0)
#define INF 1000000000
#define LINF 1000000000000000000LL
#define eps 1e-8
#define LL long long
using namespace std;
const int maxn = 1e8+10;
typedef unsigned int UI;
UI tmp[5800000];
int vis[maxn/32+10];
int p[5800000],cnt;
void init(){
cnt=0;
p[0]=tmp[0]=2;
cnt++;
IFOR(i,3,maxn-1,2){
if(!(vis[i/32]&(1<<(i%32)))){//用位图压缩节省空间
p[cnt]=i;
tmp[cnt]=tmp[cnt-1]*i;
cnt++;
IFOR(j,3*i,maxn-1,2*i) vis[j/32]|=(1<<(j%32));
}
}
}
UI solve(int n){
int pos = upper_bound(p,p+cnt,n)-p-1;
UI ans = tmp[pos];
for(int i=0;i<cnt&&p[i]*p[i]<=n;i++){
int mul = p[i];
int ff=p[i]*p[i];
while(ff/mul==p[i]&&ff<=n){
mul=mul*p[i];
ff=ff*p[i];
}
ans=ans*(mul/p[i]);
}
return ans;
}
int main()
{
init();
int t,cas=1,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("Case %d: %u
",cas++,solve(n));
}
return 0;
}
2,1~n中最小公倍数等于n的数的对数 lightoj 1236传送门
非常明显这些数都是 n 的约数，
然后n=p1^a1*p1^a2*p3^a3...*pn^an;
对这两个数素因子分解要使得的每个素数ai的最高次等于ai,
因此对于每个因子的可能方案就有 (ai+1)*2-1;
代码例如以下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1e7+10;
int p[maxn/5],tot;
bool vis[maxn];
void init(){
tot=0;
memset(vis,0,sizeof(vis));
for(int i=2;i<maxn;i++){
if(!vis[i]){
p[tot++]=i;
for(int j=i+i;j<maxn;j+=i)
vis[j]=1;
}
}
}
int main()
{
init();
int t,cas=1;
scanf("%d",&t);
while(t--){
long long n;
scanf("%lld",&n);
long long ans = 1;
for(int i=0;i<tot&&p[i]*p[i]<=n;i++){
if(n%p[i]==0){
long long cnt = 0;
while(n%p[i]==0)cnt++,n/=p[i];
ans=ans*(cnt*2+1);
}
}
if(n>1) ans*=3;
ans=ans/2+1;
printf("Case %d: %lld
",cas++,ans);
}
return 0;
}
3. 1~n中随意两对数的最大公约数之和 UVA 11426传送门
我们设 f[n] = sigma(gcd(i , n)) 1<=i<n
那么 ans[n] = ans[n-1] + f[n];
在求f[n]的时候我们能够枚举gcd 然后f[n]+=gcd*phi(n/gcd);
代码例如以下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define DWN(i,h,l) for(int i=(h);i>=(l);--i)
#define IFOR(i,h,l,v) for(int i=(h);i<=(l);i+=(v))
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))
#define PI acos(-1.0)
#define INF 1000000000
#define LINF 1000000000000000000LL
#define eps 1e-8
#define maxn 4000001
#define LL long long
using namespace std;
int phi[maxn];
LL ans[maxn];
LL f[maxn];
void init(){
FOR(i,1,maxn-1) phi[i]=i;
IFOR(i,2,maxn-1,2) phi[i]=phi[i]>>1;
IFOR(i,3,maxn-1,2){
if(phi[i]==i){
IFOR(j,i,maxn-1,i)
phi[j]=phi[j] -phi[j]/i;
}
}
}
void solve(){
CLR(ans);
init();
FOR(i,1,maxn-1){
IFOR(j,i+i,maxn,i)
f[j]=f[j]+(LL)i*phi[j/i];
}
ans[1]=f[1];
FOR(i,2,maxn-1) ans[i]=ans[i-1]+f[i];
}
int main()
{
solve();
int n;
while(~scanf("%d",&n)&&n){
printf("%lld
",ans[n]);
}
return 0;
}
4.sigma(i,n) (1<=i<=n)
传送门
分析：
两个数的最小公倍数 = x*n/gcd(x,n);我们如果与n的最大公约数为g;
则与n的最大公约数的和g的最小公倍数的和为 n/g * (x1 + x2 + x3 + x(phi[n/g]))
小于等于n与n的最大公约数为g的数的个数为 Phi[n/h] 这里的phi表示的是欧拉函数
另一个结论就是 小于等于x与x互质的数的和 = phi[x]*x/2;
证明：
if gcd(n,i)=1 then gcd(n,n-i)=1 (1<=i<=n)
反证法：
假设存在K!=1使gcd(n,n-i)=k,那么(n-i)%k==0
而n%k=0
那么必须保证i%k=0
k是n的因子,假设i%k=0那么 gcd(n,i)=k,矛盾出现;
于是问题变的很easy： ANS=N*phi(N)/2
i,n-i总是成对出现，而且和是n
于是可能就有人问了，假设存在n-i=i那不是反复计算？
答案是不会
由于:
n=2*i->i=n/2
1.假设n是奇数，那么n!=2*i,自然也不存在 n-i=i和反复计算之说
2.假设n是偶数,n=2*i成立,gcd(n,n/2)必定为n的一个因子,这个因子为1当且仅当n==2
于是对于n>2的偶数。绝对不存在gcd(n,n/2)=1所以更别说什么反复计算了
对于n==2
ans=2*1/2=1，正好也满足
所以得到终于公式：
ans=N*phi(N)/2
因此这道题目的终于公式就是 n*sigma(phi[n/x]*n/x/2) x|n;
代码例如以下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,l,h) for(int i=(l);i<=(h);++i)
#define DWN(i,h,l) for(int i=(h);i>=(l);--i)
#define IFOR(i,h,l,v) for(int i=(h);i<=(l);i+=(v))
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define MAX3(a,b,c) max(a,max(b,c))
#define MAX4(a,b,c,d) max(max(a,b),max(c,d))
#define MIN3(a,b,c) min(a,min(b,c))
#define MIN4(a,b,c,d) min(min(a,b),min(c,d))
#define PI acos(-1.0)
#define INF 1000000000
#define LINF 1000000000000000000LL
#define eps 1e-8
#define maxn 1000001
#define LL long long
using namespace std;
//const LL mod = 1e9+7;
int phi[maxn];
void init(){
FOR(i,1,maxn-1) phi[i]=i;
IFOR(i,2,maxn-1,2) phi[i]=phi[i]>>1;
IFOR(i,3,maxn-1,2){
if(phi[i]==i){
IFOR(j,i,maxn-1,i)
phi[j]=phi[j] -phi[j]/i;
}
}
}
LL ans[maxn];
void solve()
{
init();
int i,j;
FOR(i,1,maxn-1){
IFOR(j,i,maxn-1,i)
ans[j]=ans[j]+(LL)phi[j/i]*(LL)j/i/2;
}
}
int main()
{
solve();
int n,t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%lld
",(ans[n]+1)*n);
}
return 0;
}