题目描述

输入

一行，包含两个整数N，M。

输出

1个整数，FHT(N,M) mod 1000000007的值。

样例输入

3 4

样例输出

1

数据范围

对于 40% 的数据，1 ≤ N，M ≤ 1000

对于 60% 的数据，1 ≤ N，M ≤ 10^6

对于 100% 的数据，1 ≤ N，M ≤ 10^9

解法

答案=ans(n)*ans(m) (其中ans(n)=sigma(n%i))；

那么现在只用考虑ans(n)怎么求。

ans(n)=sigma(n mod i)

=sigma(n-i*(n div i))

=n^2-sigma(i)*sigma(n div i)

由于sigma(n div i)最多只有n^0.5种取值。所以可以分段计算。

证明：

令i=1..n^0.5，那么对应的n div i区间就在[n^0.5,n]，所以约数最多有2*n^0.5个。

代码

#include<iostream>

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<algorithm>

#define ll long long

#define sqr(x) ((x)*(x))

#define ln(x,y) int(log(x)/log(y))

using namespace std;

const char* fin="aP1.in";

const char* fout="aP1.out";

const int inf=0x7fffffff;

const int mo=1000000007;

int read(){

    int x=0;

    char ch=getchar();

    while (ch<'0' || ch>'9') ch=getchar();

    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();

    return x;

}

int n,m,i,j,k;

ll ans,tmp;

ll work(int a,int b){

    ll i,j=1,k=0,num,tmp,st=a;

    while (a){

        num=(a-b)/(j+1)+((a-b)%(j+1)?1:0);

        if (num<=100) {

            break;

        }

        tmp=b+num*j-j;

        k=(k+(b+tmp)*num/2)%mo;

        a-=num;

        b=(tmp+j)%a;

        j++;

    }

    for (;a;a--) k=(k+(st%a))%mo;

    return k;

}

int main(){

    scanf("%d%d",&n,&m);

    ans=(work(n,0)*work(m,0))%mo;

    printf("%lld",ans);

    return 0;

}

启发

n%i=n-n div i*i。

当i=1..n时，n div i最多有n^0.5个取值，所以可以分段计算。