Hillan and the girl

Time Limit: 12000/6000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Problem Description

“WTF!
While everyone has his girl(gay) friend, I only have my keyboard!”
Tired of watching others' affair, Hillan burst into scream, which made
him decide not to hold it back.
“All right, I am giving you a
question. If you answer correctly, I will be your girl friend.” After
listening to Hillan, Girl replied, “What is the value of ∑ni=1∑mj=1f(i,j), where f(i,j)=0 if gcd(i,j) is a square number and f(i,j)=1 if gcd(i,j) is not a square number(gcd(i,j) means the greatest common divisor of x and y)?”
But Hillan didn't have enough Intelligence Quotient to give the right answer. So he turn to you for help.

Input

The first line contains an integer T(1≤T≤10,000)——The number of the test cases.
For each test case, the only line contains two integers n,m(1≤n,m≤10,000,000) with a white space separated.

Output

For each test case, the only line contains a integer that is the answer.

Sample Input

2
1 2333333
10 10

Sample Output

0
33

Hint

In the first test case, obviously $f\left(i,j\right)$ always equals to 0, because $i$ always equals to 1 and $\gcd\left(i,j\right)$ is always a square number(always equals to 1).

Source

BestCoder Round #79 (div.2)

min(n,m) min(n/k,m/k)

思路:首先推到∑ 　　　　∑　mu(d) * [n/k/d] * [m/k/d]; k为完全平方数；

　　　　　　k=1　　　d=1

　　　令T=k*d;

　　　可得:

　　　　　　min(n,m)　　　　　　　　　　　　　　　　　　　　

　　　　　　∑　　　[n/T] * [m/T] ∑ mu(T/k) ;

　　　　　　T　　　　　　　　　　k|T

　　　　　　令gg数组等于 ∑ mu(T/k) 相当于原来的mu函数;

　　　　　　　　　　　　 k|T

　　　　　　和原来一样分块即可；

#include<bits/stdc++.h>

using namespace std;

#define ll __int64

#define esp 0.00000000001

#define pi 4*atan(1)

const int N=1e7+,M=1e7+,inf=1e9+,mod=1e9+;

int mu[N], p[N], np[N], cnt, sum[N];

ll gg[N];

void init() {

    mu[]=;

    for(int i=; i<N; ++i) {

        if(!np[i]) p[++cnt]=i, mu[i]=-;

        for(int j=; j<=cnt && i*p[j]<N; ++j) {

            int t=i*p[j];

            np[t]=;

            if(i%p[j]==) { mu[t]=; break; }

            mu[t]=-mu[i];

        }

    }

    for(int i=;i*i<N;i++)

    {

        for(int t=i*i;t<N;t+=(i*i))

        sum[t]+=mu[t/i/i];

    }

    for(int i=;i<N;i++)

    gg[i]=gg[i-]+sum[i];

}

ll getans(ll b,ll d)

{

    if(b>d)swap(b,d);

    ll ans=;

    for(ll L=,R=;L<=b;L=R+)

    {

        R=min(b/(b/L),d/(d/L));

        ans+=(b/L)*(d/L)*(gg[R]-gg[L-]);

    }

    return ans;

}

int main()

{

    int T;

    init();

    scanf("%d",&T);

    while(T--)

    {

        ll b,d;

        scanf("%I64d%I64d",&b,&d);

        printf("%I64d\n",(b*d)-getans(b,d));

    }

    return ;

}

巴特西

hdu 5663 Hillan and the girl 莫比乌斯反演

Hillan and the girl

最新文章

热门文章