果皇的矩阵[matrix]

#1101. 果皇的矩阵[matrix]

题目描述

输入格式

一行两个数，表示 N,M。

输出格式

一行一个数，表示答案对 10^9+7 取模后的结果

样例

样例输入

3 3

样例输出

38

数据范围与提示

数据范围

100%的数据， N,M<=10^5.

随便推推式子就好了，虽然不会证复杂度。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define ll long long
#define maxn 100005
using namespace std;
const int ha=1000000007;
const int mo=1000000006;
int zs[maxn],t=0,miu[maxn];
bool v[maxn];

inline int add(int x,int y){
	x+=y;
	return x>=ha?x-ha:x;
}

inline int ksm(int x,int y){
	int an=1;
	for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
	return an;
}

inline void init(){
	miu[1]=1;
	for(int i=2;i<=100000;i++){
		if(!v[i]) zs[++t]=i,miu[i]=-1;
		for(int j=1,u;j<=t&&(u=zs[j]*i)<=100000;j++){
			v[u]=1;
			if(!(i%zs[j])) break;
			miu[u]=-miu[i];
		}
	}
}

inline int calc(int base,int x,int y){
	if(base==1) return x*(ll)y%ha;
	int an=0,T=(y+1);
	if(T>=mo) T-=mo;
	for(int i=1,tmp=base;i<=x;i++,tmp=tmp*(ll)base%ha){
		an=add(an,add(ksm(tmp,T),ha-1)*(ll)ksm(add(tmp,ha-1),ha-2)%ha);
	}
	an=add(an,ha-x);
	return an;
}

inline int solve(int x,int N,int M){
	int an=0;
	for(int d=1,dn,dm;d<=N;d++){
		dn=N/d,dm=M/d;
		an=add(an,calc(ksm(d,d*(ll)x%mo),dn,dm));
	}
	return an;
}

int n,m,ans;
int main(){
	init();
	scanf("%d%d",&n,&m);
	if(n>m) swap(n,m);
	for(int i=1;i<=n;i++) if(miu[i]){
		ans=add(ans,add(ha,solve(i*(ll)i%mo,n/i,m/i)*miu[i]));
	}
	printf("%d
",ans);
	return 0;
}