QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #345984 | #4895. Lovely Dogs | zzafanti | 0 | 167ms | 29236kb | C++20 | 1.7kb | 2024-03-07 18:55:26 | 2024-03-07 18:55:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using E=long long;
E ksm(E a,E b){
E ret=1;
while(b){
if(b&1) ret=ret*a;
if(ret>200000) return 200001;
a=a*a;
b>>=1;
}
return ret;
}
int main(){
#ifdef zzafanti
freopen("in.in","r",stdin);
#endif // zzafanti
cin.tie(nullptr),cout.tie(nullptr)->sync_with_stdio(false);
int n,d;
cin>>n>>d;
vector<int> a(n+1);
for(int i=1; i<n; i++){
int x,y;
cin>>x>>y;
}
for(int i=1; i<=n; i++) cin>>a[i];
vector<int> mu(n+1),primes,st(n+1),w(n+1);
mu[1]=w[1]=1;
for(int i=2; i<=n; i++){
if(!st[i]){
mu[i]=w[i]=-1;
primes.emplace_back(i);
}
for(auto j:primes){
if(i*j>n) break;
st[i*j]=1;
w[i*j]=w[i]*w[j];
if(i%j==0){
mu[i*j]=0;
break;
}
mu[i*j]=mu[i]*mu[j];
}
}
vector<vector<int>> divs(n+1);
vector<E> sum(n+1);
for(int i=1; i<=n; i++){
for(int j=i; j<=n; j+=i){
sum[i]+=w[j];
divs[j].emplace_back(i);
}
}
int ans=0;
for(int i=1; i<=n; i++){
E x=0;
for(auto t:divs[i]){
int tmp=ksm(t,d+1);
if(tmp>n) continue;
x+=mu[t]*sum[tmp/__gcd(tmp,i)];
}
ans+=w[i]*x;
}
E T=0;
for(int i=1; i<=n; i++){
E x=0;
for(auto t:divs[i]){
E tmp=ksm(t,d+1);
if(i*1ll*i%tmp==0) x+=mu[t];
}
T+=w[i]*w[i]*x;
st[i]=x;
}
cout<<(ans-T)/2+T<<'\n';
for(int i=2; i<=n; i++){
cout<<w[i]*w[i]*st[a[i]]<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3628kb
input:
20 2 18 8 18 11 13 19 10 8 9 11 4 8 9 15 9 17 2 1 13 18 20 18 1 8 12 17 7 16 5 11 16 15 6 19 14 16 1 3 2 15 5 13 20 6 16 18 9 19 17 7 14 10 11 3 1 12 4 8
output:
15 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 0 0 0
result:
wrong answer 1st words differ - expected: '16', found: '15'
Subtask #2:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 1ms
memory: 3892kb
input:
2000 1 134 1468 867 1750 351 1220 1690 1888 1685 134 585 282 1142 643 206 271 260 1833 1987 770 1029 1667 322 1371 341 518 601 915 119 893 1933 1502 951 1785 1056 1630 1957 1208 96 55 1508 1212 331 427 505 151 1378 1486 1545 697 1459 629 202 997 180 1917 1638 1177 1244 1896 302 658 1433 1605 1318 19...
output:
-97 -1 -1 -1 0 1 1 -1 1 0 0 0 0 0 0 0 0 1 0 1 -1 -1 0 1 0 0 0 0 0 0 -1 0 0 1 0 -1 0 -1 -1 0 0 0 -1 0 1 0 0 -1 0 0 0 1 0 -1 1 0 1 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 -1 1 1 0 0 0 0 0 1 1 0 -1 -1 0 0 0 0 0 0 0 -1 0 1 1 0 1 0 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 -1 -1 -1 0 0 0 0 -1 1 0 0 1 0 0 0 1 0 1 0 0 0 0 -1 ...
result:
wrong answer 1st words differ - expected: '581', found: '-97'
Subtask #3:
score: 0
Runtime Error
Test #45:
score: 0
Runtime Error
input:
200000 20 117994 12616 53490 106425 103660 50033 132640 78252 58384 19939 69183 10015 39098 165030 179856 130356 65245 57831 18234 83378 4240 154896 177149 102260 4634 180087 132390 19627 98506 60775 1890 120740 87908 21917 41323 192721 181885 96684 69412 139951 9800 38301 59025 29879 186185 81402 1...
output:
result:
Subtask #4:
score: 0
Wrong Answer
Test #50:
score: 0
Wrong Answer
time: 162ms
memory: 29208kb
input:
200000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
-16405 0 0 0 1 0 -1 0 -1 0 0 0 0 0 -1 0 0 0 0 0 0 1 1 0 0 0 1 1 -1 0 1 0 0 1 0 0 0 0 1 -1 0 0 0 -1 0 0 0 0 0 -1 1 0 -1 0 -2 -1 0 1 -1 0 -1 0 0 0 0 0 0 1 0 0 0 -1 1 -1 0 0 0 0 0 -1 1 0 0 1 0 0 0 0 0 0 0 1 0 -2 0 0 1 -1 0 0 1 0 0 -1 0 -2 0 1 0 0 0 0 0 -1 0 0 0 0 -1 -1 0 -1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 ...
result:
wrong answer 1st words differ - expected: '-44916', found: '-16405'
Subtask #5:
score: 0
Wrong Answer
Test #55:
score: 0
Wrong Answer
time: 163ms
memory: 29236kb
input:
200000 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
output:
-16405 -1 0 0 0 1 0 0 0 -1 0 0 0 1 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 -1 0 1 -1 0 1 1 0 -1 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 0 0 -2 -1 1 0 0 0 0 0 0 -1 0 0 -2 0 0 0 -1 0 0 -2 0 0 -1 0 0 -1 0 0 0 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 -1 0 0 1 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 1st words differ - expected: '-44916', found: '-16405'
Subtask #6:
score: 0
Wrong Answer
Test #78:
score: 0
Wrong Answer
time: 33ms
memory: 9392kb
input:
50000 1 8097 41839 17674 41774 40520 8024 5786 38261 20664 43471 1217 49276 11185 40807 14186 25584 31704 14814 42333 41475 13053 39565 45938 30104 5826 39463 5031 10814 43784 6042 58 33849 42978 18978 36307 33276 34769 4351 27884 37532 27528 29431 29451 39345 10946 9667 19016 47269 7911 30103 10308...
output:
-6899 1 0 0 0 -1 0 -1 -1 0 0 0 1 0 -1 0 1 0 -1 0 0 0 0 0 1 1 1 0 0 -1 0 0 -1 1 0 0 -1 0 0 0 -1 0 1 0 0 1 1 2 0 0 1 0 1 0 0 -1 -1 -1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 1 2 0 -1 0 0 -1 -1 0 0 -1 2 0 0 0 0 0 -1 -1 0 -1 0 0 0 1 0 -1 0 1 -1 0 -1 0 -1 -1 1 1 1 0 0 0 0 1 0 -1 0 0 1 0 0 ...
result:
wrong answer 1st words differ - expected: '-9152', found: '-6899'
Subtask #7:
score: 0
Wrong Answer
Test #103:
score: 0
Wrong Answer
time: 167ms
memory: 29160kb
input:
200000 1 118863 188865 188022 168616 118976 119404 178852 33449 81624 40431 151228 160976 68943 136313 57200 117631 147789 139875 100240 55537 164811 145415 103548 186750 15010 168029 155731 107005 69836 1502 86171 122700 83448 131948 189162 94464 128210 2509 49724 183329 174782 192641 27687 71315 1...
output:
-16405 0 0 0 0 0 0 -1 0 0 1 0 -1 0 0 2 -1 0 -2 1 0 0 0 0 0 0 0 0 -1 1 -1 0 0 1 0 0 0 -2 0 0 1 1 -1 0 0 0 0 0 -1 1 1 0 0 2 -1 -1 0 -1 0 0 1 0 0 0 0 0 1 0 -1 0 0 0 -2 0 -1 0 0 0 -1 1 0 1 1 1 0 0 0 0 0 -1 1 0 1 0 0 0 0 -1 -1 -1 1 1 0 -1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 -1 0 1 0 -1 -1 1 1 0 -1 0 -1 1 1 -1 ...
result:
wrong answer 1st words differ - expected: '-44916', found: '-16405'