結果
問題 | 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 1000000001int 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;}