結果
問題 | No.1200 お菓子配り-3 |
ユーザー |
![]() |
提出日時 | 2020-08-29 03:48:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 445 ms / 4,000 ms |
コード長 | 2,772 bytes |
コンパイル時間 | 3,067 ms |
コンパイル使用メモリ | 136,964 KB |
最終ジャッジ日時 | 2025-01-13 19:55:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<ll, int> P; ll powmod(__int128_t a, ll k, ll m){ __int128_t ap=a, ans=1; while(k){ if(k&1){ ans*=ap; ans%=m; } k>>=1; ap=ap*ap%m; } return ans; } bool is_prime(ll n){ if(n<=1 || !(n&1)) return (n==2); ll d=n-1; int k=0; while(!(d&1)){ d>>=1; k++; } vector<ll> va{2, 325, 9375, 28178, 450775, 9780504, 1795265022}; // http://miller-rabin.appspot.com/ for(auto aa:va){ ll a=aa%n; if(a==0) continue; bool comp=1; ll ap=powmod(a, d, n); if(ap==1 || ap==n-1) continue; for(int r=1; r<k; r++){ ap=(__int128_t)ap*ap%n; if(ap==n-1){ comp=0; break; } } if(comp) return false; } return true; } ll gcd(ll a, ll b){ if(a==0) return b; if(b==0) return a; if(a<0) a=-a; if(b<0) b=-b; const int s=__builtin_ctzll(a|b); a>>=__builtin_ctzll(a); while(b){ b>>=__builtin_ctzll(b); if(a>b) swap(a, b); b-=a; } return a<<s; } ll rho(ll n, ll& c){ if(!(n&1)) return 2; while(1){ ll x=2, y=2, d=1; while(d==1){ x=((__int128_t)x*x+c)%n; y=((__int128_t)y*y%n+c)%n; y=((__int128_t)y*y%n+c)%n; d=gcd(abs(x-y), n); } if(d==n){ c++; continue; } return d; } } vector<pair<ll, int>> factorize(ll n){ if(n<=1){ vector<pair<ll, int>> ret; return ret; } map<ll, int> mp; vector<ll> v(1, n); ll c=1; while(!v.empty()){ ll x=v.back(); v.pop_back(); if(is_prime(x)){ mp[x]++; continue; } ll p=rho(x, c); v.push_back(p); v.push_back(x/p); } vector<pair<ll, int>> ret; for(auto p:mp) ret.push_back(p); return ret; } ll calc(ll a, ll s, ll x, ll y){ if(a==0) return 0; if(a==1){ if(x==y) return s-1; else return 0; } if(x<=s) return 0; if((x-s)%(a-1)==0 && (x-s)/(a-1)<s) return 1; else return 0; } void dfs(int k, ll d, ll x, ll y, vector<P> &v, ll &ans){ if(k==v.size()){ ans+=calc(d-1, (x+y)/d, x, y); return; } ll q=1; for(int i=0; i<=v[k].second; i++){ dfs(k+1, d*q, x, y, v, ans); q*=v[k].first; } } ll solve(ll x, ll y){ ll ans=0; auto v=factorize(x+y); dfs(0, 1, x, y, v, ans); return ans; } int main() { int s; cin>>s; while(s--){ ll x, y; cin>>x>>y; cout<<solve(x, y)<<endl; } return 0; }