結果
問題 | No.1411 Hundreds of Conditions Sequences |
ユーザー |
![]() |
提出日時 | 2021-02-27 00:12:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 208 ms / 2,000 ms |
コード長 | 1,274 bytes |
コンパイル時間 | 3,847 ms |
コンパイル使用メモリ | 258,500 KB |
最終ジャッジ日時 | 2025-01-19 07:26:13 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 62 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:27:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 27 | scanf("%d",&A[i]); | ~~~~~^~~~~~~~~~~~
ソースコード
#include <stdio.h> #include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint1000000007; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main(){ vector<int> isp(1000001,-1); vector<int> p; for(int i=2;i<isp.size();i++){ if(isp[i]==-1){ p.push_back(i); for(int j=i;j<isp.size();j+=i)isp[j] = i; } } int N; cin>>N; vector<int> A(N); mint sum = 1; vector<int> cnt(1000001,0); rep(i,N){ scanf("%d",&A[i]); cnt[A[i]]++; sum *= A[i]; } vector<int> cnt2(1000001,0); rep(i,p.size()){ long long cur = p[i]; while(cur <= 1000000){ for(int j=cur;j<=1000000;j+=cur){ cnt2[cur] += cnt[j]; } if(cnt2[cur]>=2){ sum /= mint(p[i]).pow(cnt2[cur]-1); } cur *= p[i]; } } vector<mint> ans(N,0); //cout<<sum.val()<<endl; rep(i,N){ mint temp = sum / A[i]; map<int,int> mp; int t = A[i]; while(t!=1){ mp[isp[t]]++; t/=isp[t]; } for(auto a:mp){ int x = 1; rep(j,a.second){ x *= a.first; if(cnt2[x]>=2){ temp *= a.first; } } } ans[i] = temp; } sum = 1; rep(i,N){ sum *= A[i]; } rep(i,N){ ans[i] = sum / A[i] - ans[i]; } rep(i,N){ cout<<ans[i].val()<<endl; } return 0; }