naoya_t@topcoder

SRM458 Div1 Hard: ModuloFourDivisor

過去問, 練習 | 22:39 |

昨日の900点問題を解いてみた。

Nの約数を列挙するためには素因数分解すればいいんですが…

最初、オイラーのφ関数がどうのとかあれこれ考えていたのですが、ここではmod 4だけが問題になっているので、4で割った余りがそれぞれ0,1,2,3な素数（※0は無いですね。2は2だけ）は同一視して

N = 2^S x (4k+1)^T x (4k+3)^U

が見えたら解けたも同然...

a,c

4で割って余りが0になるのはS≧2な全パターンなので

S=0,S=1:

　a = 0

S≧2:

　a = [2..S]x[0..T]x[0..U] = (S-1)(T+1)(U+1) > 0

同様に、余りが2になるのはS=1な全パターンなので

S=0:

　c = 0

S>=1:

　c = [1]x[0..T]x[0..U] = (T+1)(U+1) ≧1

c≠0のとき、aはcで割り切れなければならない。∵a=(S-1)c

あと

• a≠0のとき（Nは4の倍数）には必ずc≠0（2の倍数）
• c=0（Nは2の倍数でない）のときには必ずa=0（当然4の倍数でもない）

b,d

余りが1(または3)になるのはS=0の場合。Uが偶数なら1,奇数なら3になる。Tはいくつでも関係ない。よって

b = [0]x[0..T]x[0,2,4,...n<=U] = (T+1)[(U+2)/2] ≧1

d = [0]x[0..T]x[1,3,5,...m<=U] = (T+1)[(U+1)/2] ≧0

• U=0のときd=0
• Uが奇数のときb=d
• Uが偶数のときb=d+(T+1)

という関係が成り立つ。b≠dのとき [(U+2)/2]=[(U+1)/2]+1 のため (T+1) はbとdの最大公約数に等しいことも使える。

• あと、c>0のときc=b+d

以上の条件をクリアするものをA,B,C,Dの全組み合わせ（高々50^4通り）の中から数え上げればよい。

Mediumより簡単じゃないか...

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

ll gcd(ll m, ll n)
{
  if (m == 0 || n == 0) return 0;
  if (m == 1 || n == 1) return 1;
  if (m == n) return m;
  while (1) {
    if (m == 0) return n;
    if (n == 0) return m;
    if (m > n) m %= n; else n %= m;
  }
}

class ModuloFourDivisor {
  bool possible(ll a,ll b,ll c,ll d){
    if (b==0) return false;
    if (a>0 && c==0) return false;
    if (c==0 && a>0) return false;
    if (c>0) {
      if (a % c) return false;
      if (b+d != c) return false;
    }
    if (d==0 || b==d) return true;
    if (b == d+gcd(b,d)) return true; // ※※
    return false;
  }

 public:
  int countQuadruplets(vector<long long> A, vector<long long> B, vector<long long> C, vector<long long> D) {
    int cnt=0;
    tr(A,at) tr(B,bt) tr(C,ct) tr(D,dt)
      if (possible(*at,*bt,*ct,*dt)) cnt++;
    return cnt;
  }
};

最初、※※のチェックをc>0のときにしかしていなくてfailed system test → そこを直したら通った