結果
| 問題 | No.377 背景パターン |
| ユーザー |
 uwi
|
| 提出日時 | 2016-06-05 15:19:33 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 384 ms / 5,000 ms |
| コード長 | 8,022 bytes |
| コンパイル時間 | 4,262 ms |
| コンパイル使用メモリ | 86,592 KB |
| 実行使用メモリ | 40,408 KB |
| 最終ジャッジ日時 | 2024-10-08 15:41:48 |
| 合計ジャッジ時間 | 6,962 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 14 |
ソースコード
package q5xx;import java.io.ByteArrayInputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.Arrays;import java.util.InputMismatchException;public class Q561_3 {InputStream is;PrintWriter out;String INPUT = "";// 10^9:1344// 2^31:1600int[] divs(int n){int[] high = new int[1344];int[] low = new int[1344];int p = 0, q = 0;for(int i = 1;i*i <= n;i++){if(n % i == 0){low[p++] = i;if(i*i < n)high[q++] = n/i;}}while(q-1 >= 0){low[p++] = high[q-1];q--;}return Arrays.copyOf(low, p);}void solve(){int h = ni(), w = ni(), K = ni();int[] dhs = divs(h);int[] dws = divs(w);int mod = 1000000007;int[] numhs = new int[dhs.length];for(int i = dhs.length-1;i >= 0;i--){numhs[i] = h/dhs[i];for(int j = i+1;j < dhs.length;j++){if(dhs[j] % dhs[i] == 0){numhs[i] -= numhs[j];}}}int[] numws = new int[dws.length];for(int i = dws.length-1;i >= 0;i--){numws[i] = w/dws[i];for(int j = i+1;j < dws.length;j++){if(dws[j] % dws[i] == 0){numws[i] -= numws[j];}}}long ret = 0;long big = 8L*mod*mod;for(int i = 0;i < dhs.length;i++){for(int j = 0;j < dws.length;j++){long x = h/dhs[i];long y = w/dws[j];long z = x*(y/gcd(x,y));long key = (long)h*w/z;if(!cache.containsKey(key)){cache.put(key, pow(K, (long)h*w/z, mod));}ret += cache.get(key) * numhs[i] % mod * numws[j];if(ret >= big)ret -= big;}}ret = ret % mod * invl(h, mod) % mod * invl(w, mod) % mod;out.println(ret);}static LongHashCounterL cache = new LongHashCounterL();public static long gcd(long a, long b) {while (b > 0) {long c = a;a = b;b = c % b;}return a;}public static long invl(long a, long mod) {long b = mod;long p = 1, q = 0;while (b > 0) {long c = a / b;long d;d = a;a = b;b = d % b;d = p;p = q;q = d - c * q;}return p < 0 ? p + mod : p;}public static long pow(long a, long n, long mod) {// a %= mod;long ret = 1;int x = 63 - Long.numberOfLeadingZeros(n);for (; x >= 0; x--) {ret = ret * ret % mod;if (n << 63 - x < 0)ret = ret * a % mod;}return ret;}public static class LongHashCounterL {public long[] keys;public long[] allocated;private int scale = 1<<2;private int rscale = 1<<1;private int mask = scale-1;public int size = 0;public LongHashCounterL(){allocated = new long[scale];keys = new long[scale];}public boolean containsKey(long x){int pos = h(x)&mask;while(allocated[pos] != 0){if(x == keys[pos])return true;pos = pos+1&mask;}return false;}public long get(long x){int pos = h(x)&mask;while(allocated[pos] != 0){if(x == keys[pos])return allocated[pos];pos = pos+1&mask;}return 0;}public long inc(long x, long v){int pos = h(x)&mask;while(allocated[pos] != 0){if(x == keys[pos]){allocated[pos] += v;return allocated[pos];}pos = pos+1&mask;}if(size == rscale){resizeAndPut(x, v);}else{keys[pos] = x;allocated[pos] = v;}size++;return v;}public long put(long x, long v){int pos = h(x)&mask;while(allocated[pos] != 0){if(x == keys[pos]){long oldval = allocated[pos];allocated[pos] = v;return oldval;}pos = pos+1&mask;}if(size == rscale){resizeAndPut(x, v);}else{keys[pos] = x;allocated[pos] = v;}size++;return 0;}public boolean remove(long x){int pos = h(x)&mask;while(allocated[pos] != 0){if(x == keys[pos]){size--;// take last and fill rmposint last = pos;pos = pos+1&mask;while(allocated[pos] != 0){int lh = h(keys[pos])&mask;// lh <= last < posif(lh <= last && last < pos ||pos < lh && lh <= last ||last < pos && pos < lh){keys[last] = keys[pos];allocated[last] = allocated[pos];last = pos;}pos = pos+1&mask;}keys[last] = 0;allocated[last] = 0;return true;}pos = pos+1&mask;}return false;}private void resizeAndPut(long x, long v){int nscale = scale<<1;int nrscale = rscale<<1;int nmask = nscale-1;long[] nallocated = new long[nscale];long[] nkeys = new long[nscale];for(int i = next(0);i < scale;i = next(i+1)){long y = keys[i];int pos = h(y)&nmask;while(nallocated[pos] != 0)pos = pos+1&nmask;nkeys[pos] = y;nallocated[pos] = allocated[i];}{int pos = h(x)&nmask;while(nallocated[pos] != 0)pos = pos+1&nmask;nkeys[pos] = x;nallocated[pos] = v;}allocated = nallocated;keys = nkeys;scale = nscale;rscale = nrscale;mask = nmask;}public int next(int itr){while(itr < scale && allocated[itr] == 0)itr++;return itr;}private int h(long x){x ^= x>>>33;x *= 0xff51afd7ed558ccdL;x ^= x>>>33;x *= 0xc4ceb9fe1a85ec53L;x ^= x>>>33;return (int)x;}@Overridepublic String toString(){StringBuilder sb = new StringBuilder();for(int i = next(0);i < scale;i = next(i+1)){sb.append(",");sb.append(keys[i] + ":" + allocated[i]);}return sb.length() == 0 ? "" : sb.substring(1);}}void run() throws Exception{is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());out = new PrintWriter(System.out);long s = System.currentTimeMillis();solve();out.flush();if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");}public static void main(String[] args) throws Exception { new Q561_3().run(); }private byte[] inbuf = new byte[1024];private int lenbuf = 0, ptrbuf = 0;private int readByte(){if(lenbuf == -1)throw new InputMismatchException();if(ptrbuf >= lenbuf){ptrbuf = 0;try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }if(lenbuf <= 0)return -1;}return inbuf[ptrbuf++];}private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }private double nd() { return Double.parseDouble(ns()); }private char nc() { return (char)skip(); }private String ns(){int b = skip();StringBuilder sb = new StringBuilder();while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')sb.appendCodePoint(b);b = readByte();}return sb.toString();}private char[] ns(int n){char[] buf = new char[n];int b = skip(), p = 0;while(p < n && !(isSpaceChar(b))){buf[p++] = (char)b;b = readByte();}return n == p ? buf : Arrays.copyOf(buf, p);}private char[][] nm(int n, int m){char[][] map = new char[n][];for(int i = 0;i < n;i++)map[i] = ns(m);return map;}private int[] na(int n){int[] a = new int[n];for(int i = 0;i < n;i++)a[i] = ni();return a;}private int ni(){int num = 0, b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private long nl(){long num = 0;int b;boolean minus = false;while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));if(b == '-'){minus = true;b = readByte();}while(true){if(b >= '0' && b <= '9'){num = num * 10 + (b - '0');}else{return minus ? -num : num;}b = readByte();}}private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }}