【問(wèn)題描述】

給出一個(gè)n*m的方陣, 請(qǐng)輸出從左下角的人的位置能看到的人數(shù)除以19268017的余數(shù)。

【輸入格式】

輸入一行兩個(gè)正整數(shù) n,m

【輸出格式】

輸出一個(gè)數(shù)，即舉報(bào) AJH 的人數(shù)除以 19268017 的余數(shù)

【樣例輸入】

3 5

【樣例輸出】

8

【數(shù)據(jù)規(guī)模與約定】

對(duì)于 30%的數(shù)據(jù)，0＜n,m≤1000

對(duì)于 60%的數(shù)據(jù)，0＜n,m≤10^5

對(duì)于 100%的數(shù)據(jù)，0＜n,m≤10^7

n,m 不保證相等

本題空間開(kāi)兩倍大（256MB）

【題解】

這道題就是求n*n范圍內(nèi)所有橫縱坐標(biāo)互質(zhì)的點(diǎn), 也就是gcd(x,y)=1.

,將f(d)定義為gcd(x,y)=d的點(diǎn)的數(shù)量, 那么自然f(1)就是互質(zhì)的點(diǎn)數(shù)了. 根據(jù)莫比烏斯反演定理用F(n)來(lái)表示f(1)就是:

這時(shí)利用莫比烏斯反演的第二種形式:
\[ F(d)=\sum _{n|d} f(d) \]
這時(shí)的莫比烏斯反演公式:

\[ f(n)=\sum_{n|d} \mu(\frac dn)F(d) \]
F(x)函數(shù)就是所有橫縱坐標(biāo)有公因數(shù)x的點(diǎn)的數(shù)量(注意這里沒(méi)有最大)

非常簡(jiǎn)單, F(1)的值顯然是m*n.

當(dāng)F(x)的參數(shù)為任意正整數(shù)時(shí), 無(wú)非就是求m, n都除以x的范圍內(nèi), F(1)的值罷了.
\[ F(x)=mn/x^2 \]
這便能O(1)求出任意F(x)值.

如果要求f(1), 代入公式:
\[ f(1)=\sum _{i=1} ^{i<=t}\mu(\frac it)F(i)=\sum _{i=1} ^{i<=t} \mu(\frac it)mn/i^2 \]
注意, 因?yàn)閚,m兩數(shù)互不相同, 所以這里的t是兩者中較小的, 因?yàn)槿绻鹖比mn其中一個(gè)大, 那么m或n除以i的時(shí)候有可能出現(xiàn)0, 這樣就沒(méi)有必要了.所以這里的t一律是m,n中較小的.

這樣, 就寫出了O(n)的算法.

但是, 可氣的是, 這么優(yōu)秀的算法竟然還能優(yōu)化

因?yàn)樵谀承r(shí)候, 隨著i的變化, 在某些區(qū)間內(nèi), m/i和n/i的積不隨i的變化而變化. 這樣就能通過(guò)前綴和的方法, 分段進(jìn)行優(yōu)化. 到時(shí)只要用前綴和求出這個(gè)區(qū)間內(nèi)μ(x)函數(shù)值的總和, 然后用總和乘這個(gè)暫時(shí)不變的積即可.

因?yàn)閙/i的變化周期和n/i的變化周期不同步, 所以要以從當(dāng)前i往后數(shù)起, 最早發(fā)生變化的i的前一個(gè)作為當(dāng)前段的終點(diǎn).

如何求這個(gè)點(diǎn)呢?

假設(shè)i現(xiàn)在是任意可能的i, n/i向下取整的值為j, 如果j大于等于i, 那么(n/j)×i=(n/i)×j, 如果j小于i, 那么這是就會(huì)出現(xiàn)(n/j)×i>=(n/i)×j的情況, 這種情況便是出現(xiàn)n/i不隨i變化的情況. 也就是說(shuō), 這個(gè)時(shí)候n/j×i中, 至少i取值從i到n/j這個(gè)區(qū)間里, n/i的值不變(可能i-1也是這樣, 但是不一定).

這樣便可以通過(guò)一個(gè)n/i值不變區(qū)間中的任意一個(gè)點(diǎn), 推導(dǎo)出這個(gè)區(qū)間的終點(diǎn). 那么, 怎么求這個(gè)起點(diǎn)呢?

很簡(jiǎn)單, 第一個(gè)區(qū)間的起點(diǎn)自然是1, 根據(jù)不重不漏原則, 接下來(lái)每個(gè)區(qū)間的起點(diǎn)就一定是上一個(gè)區(qū)間的終點(diǎn) 1.

為了保證n/i和m/i的積在區(qū)間內(nèi)不變, 我們分別尋找到對(duì)于n/i和m/i不變的區(qū)間的終點(diǎn)后, 取那個(gè)相對(duì)小的來(lái)做這個(gè)積不變區(qū)間的終點(diǎn).

接下來(lái)放代碼.

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<minmax.h>
using namespace std;
long long n, m, ans = 2/*第0行和第0列的兩個(gè)點(diǎn)提前算上*/, Mu[10000007]/*一開(kāi)始是μ(x), 后成前綴和*/, Pri[10000007]/*存所有質(zhì)數(shù)*/, t, T/*存n,m*/;
bool Isntpri[10000007]/*歐拉篩標(biāo)記*/;
inline void Read(long long& x) {//讀入模塊
    long long f = 1;
    char c = getchar();
    x = 0;
    while (c < '0' || c>'9') {
        if (c == '-')f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3)   (x << 1)   c - '0';
        c = getchar();
    }
    x *= f;
}
inline void Prime(long long n) {//歐拉篩求Mu(x)
    Mu[1] = 1;//遞推邊界
    for (register long long i = 2; i <= n; i  ) {//從2開(kāi)始遞推
        if (!Isntpri[i]) {//沒(méi)有被篩到過(guò), i是質(zhì)數(shù)
            Pri[  Pri[0]] = i;//記錄到Pri里
            Mu[i] = -1;//質(zhì)數(shù)只有一個(gè)質(zhì)因數(shù)(它本身), 所以Mu(i)等于-1
        }
        for (register long long j = 1; (j <= Pri[0]) && (i * Pri[j] <= n); j  ) {//不管i是不是質(zhì)數(shù), 都要乘部分已知質(zhì)數(shù)(積一定小于等于i^2)
            Isntpri[i * Pri[j]] = 1;//篩掉積, 積一定是合數(shù)
            if (i % Pri[j] == 0) {//當(dāng)前質(zhì)數(shù)是i的質(zhì)因數(shù)時(shí), 設(shè)i=n*Pri[j]=m*Pri[j 1], 則合數(shù)i*Pri[j]已經(jīng)被篩掉了(先篩后Break), 而Pri[j 1]*i一定會(huì)被Pri[j 1]^2篩掉(或者是被Pri[j k]篩掉)
                break;
            }//這樣便可以不重不漏O(n)篩出所有質(zhì)數(shù)
            Mu[i * Pri[j]] = -Mu[i];//別忘了處理Mu(x)(積性函數(shù)只要用一對(duì)因數(shù)的函數(shù)值相乘就好)
        }
    }
}
int main() {
    //  freopen("matrix.in", "r", stdin);
    //  freopen("matrix.out", "w", stdout);
    Read(n), Read(m);//輸入
    n--, m--;//忽略第0列和第0排
    if (!n || !m) {//m,n有0
        if (!n && !m)cout << 0 << endl;//都為0, 答案為0
        else cout << 1 << endl;//有一個(gè)為0, 答案只有1(一維的線)
        return 0;//無(wú)需多算
    }
    if (n > m) {//先用T,t表示n,m中較大的和較小的
        T = n;
        t = m;
    }
    else {
        t = n;
        T = m;
    }
    Prime(T);//歐拉篩, 求出莫比烏斯函數(shù)Mu(x)
    for (register long long i = 1; i <= T; i  ) {//這時(shí)的Mu(x)已經(jīng)不是莫比烏斯函數(shù)了, 而是莫比烏斯函數(shù)的前綴和
        Mu[i] = (Mu[i]   Mu[i - 1]) % 19268017;
    }
    for (register long long l = 1, r; l <= t; l = r   1) {//這時(shí)開(kāi)始進(jìn)行分段優(yōu)化
        if (n / (n / l) < m / (m / l)) {//之前說(shuō)的從區(qū)間任意點(diǎn)求區(qū)間終點(diǎn)的方法, 選擇較小的
            r = n / (n / l);
        }
        else {
            r = m / (m / l);
        }
        ans  = (Mu[r] - Mu[l - 1]) * (n / l) % 19268017 * (m / l) % 19268017;//這里的前綴和相減求出來(lái)的就是Mu(x)函數(shù)值從l到r的總和, 乘上這個(gè)暫時(shí)不變的積
        ans %= 19268017;
    }
    printf("%lld\n", ans);//直接輸出答案
    return 0;
}