結果
問題 |
No.1411 Hundreds of Conditions Sequences
|
ユーザー |
![]() |
提出日時 | 2021-02-26 22:05:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 452 ms / 2,000 ms |
コード長 | 2,001 bytes |
コンパイル時間 | 3,001 ms |
コンパイル使用メモリ | 184,012 KB |
最終ジャッジ日時 | 2025-01-19 05:30:44 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 62 |
ソースコード
#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> #include <list> #include <atcoder/all> #define popcount __builtin_popcount using namespace std; using namespace atcoder; typedef long long ll; typedef pair<int, int> P; vector<P> v[100010]; int emx[1000010]; int emx2[1000010]; int main() { int n; cin>>n; int a[100010]; for(int i=0; i<n; i++){ cin>>a[i]; } for(int i=0; i<n; i++){ int x=a[i]; for(int j=2; j*j<=x; j++){ if(x%j==0){ int e=0; while(x%j==0){ e++; x/=j; } v[i].push_back({j, e}); if(emx[j]<e){ emx2[j]=emx[j]; emx[j]=e; }else if(emx2[j]<e){ emx2[j]=e; } } } if(x>1){ v[i].push_back({x, 1}); if(emx[x]<1){ emx2[x]=emx[x]; emx[x]=1; }else if(emx2[x]<1){ emx2[x]=1; } } } using mint=modint1000000007; mint tot=1; for(int i=0; i<n; i++) tot*=a[i]; mint ans0=1; for(int i=2; i<1000000; i++){ if(emx[i]){ for(int j=0; j<emx[i]; j++) ans0*=i; } } for(int i=0; i<n; i++){ mint ans=ans0; for(auto q:v[i]){ int p=q.first, e=q.second; if(emx[p]==e){ for(int j=0; j<emx[p]-emx2[p]; j++) ans/=mint(p); } } ans=tot/a[i]-ans; cout<<ans.val()<<endl; } return 0; }