naoya_t@topcoder

SRM365 Div1 Easy: PointsOnCircle

過去問, 練習 | 12:52 |

300点問題・・・普通にやってたらTLE

• r^2の約数のうち、4で割って1ないし3余るものを全てカウントする必要があるが
• 約数すべて求める・・・
• やみくもに割っていくのは時間的に間に合わない
• 素因数分解して、4で割って余りの出る約数を全部見て行くか
• コーディングに時間かかったけどシステムテスト一発通過。122.65点
• Project Eulerではよくある処理だったのでSchemeでは書いた気がするが・・・ライブラリを整備したい

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

ll primes[44721];// 357768 bytes
int primes_cnt;

int e_sieve(int till)
{
  vector<bool> sieve(till+1,true);
  primes_cnt = 0;

  sieve[2] = true;
  primes[primes_cnt++] = 2;

  for (int prime=3;;) {
    primes[primes_cnt++] = prime;
    for (int i=prime*3;i<=till;i+=(prime*2)) sieve[i] = false;

    int next_prime = -1;
    for (int j=prime+2; j<=till; j+=2) {
      if (sieve[j]) { next_prime = j; break; }
    }

    if (next_prime == -1) break;
    prime = next_prime;
  }

  return primes_cnt;
}

map<int,int> prime_factors(int n)
{
  map<int,int> factors;
  for (int i=0; i<primes_cnt; i++) {
    int prime = primes[i];
    while (n % prime == 0) {
      if(found(factors,prime)) factors[prime]++;
      else factors[prime]=1;
      n /= prime;
    }
    if (n==1) return factors;
  }
  factors[n] = 1; return factors;
}

vector<ll> divisors(map<int,int> pfs){
  set<ll> s;
  s.insert(1LL);
  
  tr(pfs,it){
    ll prime=(ll)it->first,mx=it->second,n=1LL;
    set<ll> t(all(s));
    rep(i,mx) {
      n *= prime;
      tr(s,st) t.insert(n*(*st));
    }
    s=t;
  }
  vector<ll> ans(all(s));
  return ans;
}

class PointsOnCircle {
 public:
  long long count(int r) {
    // 素数を準備
    e_sieve((int)sqrt(r));

    // rを素因数分解; 2000000000 => { 2 => 10, 5 => 9 } 
    map<int,int> pfs=prime_factors(r);

    // r^2を素因数分解、というかrの結果を２乗。
    // ４で割って余りが出るものだけにしたいので、
    // ここで 2^k の係数を1以下に限定する。
    // => { 2 => (20→)1, 5 => 18 } 
    tr(pfs,it){
      it->second *= 2;
      if(it->first==2) it->second=min(2,it->second);
    }
    // 素因数分解の結果から約数を求める
    vector<ll> ds = divisors(pfs);

    // 4*(d1(n)-d3(n))を求める
    ll c=0LL;
    tr(ds,it){
      int rm=(*it)%4;
      if(rm==1) c++;
      else if(rm==3) c--;
    }
    return c<<2;
  }
};