【JZOJ2700】【GDKOI2012模拟02.01】數字

Description

Data Constraint

Solution

比賽時離正解就差一步……

我們打個表找找規律後發現：X*D(X)=i *i+9 *i *k，i∈[1,9]，那麼對于一個詢問，我們可以通過枚舉i來确定k的最大值計算數量。對于詢問[l,r]我們可以用[1,r]-[1,l-1]來解決。

問題來了：一個x*d(x)可能在不同的i中出現（如125*d(125)=1000*d(1000)）如何去重？

我們考慮

i∗i+9∗i∗k=j∗j+9∗j∗l

i∗i−j∗j=9∗(j∗l−i∗k)

找找規律找一下可能出現x*d(x)相同的i，j，一定滿足i+j=9. (i+j)∗(i−j)=9∗(j∗l−i∗k)

i−j=j∗l−i∗k

當l=k=-1時，這是一個解。那麼我們現在要讨論ax+by=c的解的數量。

若滿足 ax−by=c

a(x+bgcd(a,b))−b(y+agcd(a,b))=c

是以相鄰連個x的姐之間間隔是b/gcd(a,b)。讨論減一下就好。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=e7+;
ll test,n,m,i,t,j,k,l,x,y,z,ans; 
ll gcd(ll x,ll y){
    ll r=x%y;
    while (r) x=y,y=r,r=x%y;
    return y;
}
int main(){
//  freopen("data.in","r",stdin);
    scanf("%lld",&test);
    for (;test;test--){
        scanf("%lld%lld",&m,&n);m--;ans=;
        for (i=;i<=;i++){
            if (i*i>n) break;
            t=(n-i*i)/(*i)+;
            ans+=t;
            if (i<= && (-i)*(-i)<=n){
                k=(-i)/gcd(i,-i);
                ans-=t/k;
            }
        }
        for (i=;i<=;i++){
            if (i*i>m) break;
            t=(m-i*i)/(*i)+;
            ans-=t;
            if (i<= && (-i)*(-i)<=m){
                k=(-i)/gcd(i,-i);
                ans+=t/k;
            }
        }
        printf("%lld\n",ans);
    }
}