naoya_t@hatenablog

いわゆるチラシノウラであります

SRM713

ちょっとウォーミングアップのつもりでSRMに出てみた。
TCOではない)SRM出るのは超久しぶり。

Easy (250) PowerEquation

発想は間違ってなかったんだけど、計算が合わなくてごりごりやってるうちに終了。(0pt)

考え方

a^b = c^d になるというのは
(1) a=c=1 のとき。→ 任意のb,dで成り立つ
(2) a=cのとき。→b=dなら成り立つ。
(3) a<cのとき = (4)の左右をひっくり返したもの全て。
(4) a>cのとき。a=p^u, c=p^v と置ける共通の正の整数p,u,v (u>v) があって
 (p^u)^b = (p^v)^d ←→ p^(ub) = p^(vd) ←→ ub = vd のとき。
 1≦ a=p^u ≦ n ≦1e9, 1≦ c=p^v ≦ n ≦1e9 だから、
 ・p=1のとき… u,vは任意の数。これは (1) で既に数えてるので無視。
 ・p>1のとき… u,vには高々29までしか入らない。(∵2^29 < 1e9 < 2^30, 3^18 < 1e9 < 3^19, ...)
  ・29というのはN=1e9の場合。Nが小さければもっと低い値。
  ・u には1〜29が、vに1〜(u-1)が入る
  ・pには2〜(a=p^u がN以下に収まる数)が入る。
  ・(p^u)^b = (p^v)^d、すなわち ub = vd で、b,d に1〜Nの整数を入れて成り立つのは何通り?
  ってのを数え上げる。
  ・重複があるんだよね。p=4,u=1,v=2でも p=2,u=2,v=4 でも a=4,c=16 になる。これは u,vが互いに素なものだけ考えればよさそう。
  ・u,vが互いに素なら、ub = vd は、uで割り切れるd(※dは1..N の範囲で)だけ使えばいい。d=ukならvd=v(uk) = u(vk)、で b=vkね

「(uが決まっている時)a=p^u がN以下に収まるp」のところを正確に計算できないとやばそう。気持ち的にはNのu乗根の整数部、つまり floor(N, 1.0/u) だけど。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);++var)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

const ll M=1000000007LL;

ll ADD(ll x, ll y) { return (x+y) % M; }
ll SUB(ll x, ll y) { return (x-y+M) % M; }
ll MUL(ll x, ll y) { return x*y % M; }
ll POW(ll x, ll e) { ll v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
ll DIV(ll x, ll y) { return MUL(x, POW(y, M-2)); }

ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }

inline ll lpow(ll p, int u) {
    ll x = 1LL;
    rep(i, u) x *= p;
    return x;
}

class PowerEquation {
 public:
    int count(int _n) {
        ll N = _n;

        vector<ll> maxp(30, 1);
         // p^u ≦ N となる最大の整数pを uごとに求める。
         // u=1のとき、pは p≦N なら何でも良い。
         // u>=30のとき、2^30>1e9 となり1しか取れないので、29まで考えればいい
         // maxp[u] = floor(pow(N, 1.0/u));
        maxp[1] = N;
        ll ulimit = sqrt(N) + 1;
        for (int u=2; u<=29; ++u) {
            for (ll p=ulimit; p>=1; --p) {
                if (lpow(p, u) <= N) {
                    maxp[u] = p; ulimit = p;
                    break;
                }
            }
        }

        ll z = 0;

         // a=b=1のとき: b,dは[1..N]の範囲なら何でもいい
        z += MUL(N, N);  // 1^b = 1^d, for b=[1..N], d=[1..N]
         // a=c, b=dのとき: a,cは[1..N]の範囲なら何でもいい(がa=1はもう数えたので省く)
        z += MUL(N-1, N);  // a^b = a^b, for a=[2..N], b=[1..N]
         // その他のケース。
         // a > c, すなわち u > v を仮定して考え(て、それを2倍する)
        for (ll u=2; u<=29; ++u) {
            ll imax = maxp[u];
            if (imax == 1) break; // i=1は無視するので
             // a = i^u, i=[1..imax]だけどi=1は省く
            ll y = 0;
            for (ll v=1; v<u; ++v)  {
                 // gcd(u,v) != 1 のものは、以前に数えたものの定数倍だからもう数えない
                ll g = gcd(u, v); if (g > 1) continue;
                 // assert(gcd(u, v) == 1); // u, vは互いに素
                 // ll lcd = u/g * v, x = v*N/lcd;
                 // a = i^u, b=[1..N]の何か、c=i^v, d=[1..N]の何か、
                 // 但しub = vd で、u,vが互いに素なので
                 // vdがuで割り切れる = dがuで割り切れる、ということで
                 // d=[1..N] なら floor(N/u) 通りしかない
                ll x = N/u;
                y += MUL(imax-1, x);
            }
            z = ADD(z, y * 2);
        }
        return z;
    }
};

Medium (250)

not opened

Hard (900)

not opened

Challenge phase

他人のコードは開かず、自分の実装の続きを書いてた。
ひと握りの超人達がEasyを通しただけで、Challenge phaseも盛り上がらず。

System Test

    • -

結果

レーティングを少し落として終わった。(0pt, 1611→1574)