結果
問題 | No.1844 Divisors Sum Sum |
ユーザー |
👑 ![]() |
提出日時 | 2021-08-25 04:25:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,179 bytes |
コンパイル時間 | 3,908 ms |
コンパイル使用メモリ | 201,772 KB |
最終ジャッジ日時 | 2025-01-24 01:49:53 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 WA * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;using std::cout;using std::cin;using std::endl;using ll=long long;ll mod=1e9+7;#define rep(i,a) for (ll i=0;i<a;i++)//Nの正の約数を列挙するvector<long long> Divisors(long long N){vector<long long> p,q;long long i=1,K=0;while(i*i<N){if(N%i==0){p.push_back(i);q.push_back(N/i);K++;}i++;}if(i*i==N) p.push_back(i);for(int i=K-1;i>=0;i--){p.push_back(q[i]);}return p;}const int MAX_N=2e5;const int MAX_P=1e9;const int MAX_e=1e9;// rainy ~ 雨に打たれて ~int main() {int N;cin>>N;assert(1<=N&&N<=MAX_N);vector<ll> P(N),e(N);set<ll> appear;ll multi=MAX_P;rep(i,N){cin>>P[i]>>e[i];assert(!appear.count(P[i]));appear.insert(P[i]);assert(2<=P[i]&&P[i]<=MAX_P);assert(1<=e[i]&&e[i]<=MAX_e);rep(j,e[i]){if(multi==0) break;multi/=P[i];}}if(multi==0){cout<<"-1\n";return 0;}ll X=1;rep(i,N){rep(j,e[i]) X*=P[i];}auto p=Divisors(X);ll ans=0;for(auto x:p){auto q=Divisors(x);for(auto y:q) ans+=y;}cout<<ans%mod<<endl;}