gym 101775 D. Mr. Panda and Geometric Sequence（枚舉）

題解：枚舉所有情況，關鍵點在于首先我們先隻考慮前三個數，那麼重點是第二個數不能超過1e5。

然後我們假設倍數是

 ，這個式子應該是最簡分式，即gcd(q,p) ==1。

假設一個變量k，使得第一個數為：k*p*p，則第二個數為k*p*q，第三個數為k*q*q。如此往下枚舉。

然後往後擴充第4，5，......個的時候判斷下k%p是否為0即可。

枚舉的複雜度大概為O（nlognlogn），因為前兩個for循環是調和級數，第三個也差不多。

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int MX = 1e7+7;
int cnt;
LL a[20];
LL ans[MX];
int popcnt(LL x)
{
    int ret = 0;
    while(x){
        x /= 10;
        ++ret;
    }
    return ret;
}
int solve(LL x)
{
    return upper_bound(ans,ans+cnt,x) - ans;
}
void init()
{
    int n = 1e5;
    a[0] = 1;
    for(int i = 1; i < 16; i++) a[i] = a[i-1]*10;
    for(int p = 1; p <= n; p++){
        for(int q = p+1; q <= n/p; q++){
            if(__gcd(p,q) > 1) continue;
            for(int k = 1; k <= n/p/q; k++){
                LL x = 1LL*k*p*p;
                LL y = 1LL*k*p*q;
                LL z = 1LL*k*q*q;
                int nx = popcnt(x), ny = popcnt(y), nz = popcnt(z);
                int num = nx + ny + nz;
                if(num > 15) break;
                LL lastnum = z, lastv = x*a[ny+nz]+y*a[nz]+z;
                ans[cnt++] = lastv;

                while(1){
                    if(lastnum%p != 0) break;
                    lastnum = lastnum/p*q;
                    num += popcnt(lastnum);
                    if(num > 15) break;
                    lastv = lastv*a[popcnt(lastnum)]+lastnum;
                    ans[cnt++] = lastv;
                }
            }
        }
    }
    sort(ans,ans+cnt);

}

int main()
{
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif // LOCAL
    int T,cas = 0;
    init();
    scanf("%d",&T);
    while(T--) {
        LL l,r;
        scanf("%I64d%I64d",&l,&r);
        printf("Case #%d: %d\n",++cas,solve(r)-solve(l-1));
    }
    return 0;
}