果皇的矩阵[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\n",ans);

	return 0;

}