A - AtCoder Quiz 3
B - Triple Metre
C - X drawing 暂无
D - Destroyer Takahashi 暂无 贪心好难啊
E - Fraction Floor Sum
F - Predilection
G - GCD Permutation
H - Bullion暂无
A A A
int t;
scanf("%d", &t);
t += t>=42;
printf("AGC%03d", t);
B B B
string t = "", c;
for(int i = 1;i <= 20;i ++)t += "oxx";
cin>>c;
puts(t.find(c)<t.length()?"Yes" :"No");
E E E 分块模板
LL sum = 0, n;
scanf("%lld", &n);
for(LL l = 1, r;l <= n;l = r+1)
{
r = n/(n/l);
sum += (r-l+1)*(n/l);
}
cout<<sum<<endl;
F F F 考虑dp, d p [ i ] dp[i] dp[i] 表示把1~i划分的方案数，那么 d p [ i ] = d p [ i − 1 ] ∗ 2 dp[i] = dp[i-1]*2 dp[i]=dp[i−1]∗2 (相当于把 i − 1 i-1 i−1的方案数后面都加上 n u m [ i ] num[i] num[i]) 但这样有重复的, 重复的是前缀和相等的那部分，这个是我照着样例看的，就是这个思路。。容斥了半天结果发现之前思路错了
int n, ans = 0, l = 0; // 考虑dp, dp[i]代表 前i个数的答案
LL sum = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i ++)
{
int x;
scanf("%d", &x);
l = ans;
if(i != 1) add(ans, ans-ma[sum]);
else add(ans, 1);
ma[sum] = l;
}
add(ans, mod);
cout<<ans<<endl;
/*
0 1
377914575 2
102436426 4
102436426 6
-341739478 12
377914575 23
123690081 46
0 92
377914575 172
123690081 321
*/
G
G
G 有个枚举i的思想，但是pi不会算了，看了答案说这部分枚举可以优化具体来说就是
∑
u
=
1
n
∑
v
=
1
n
c
[
u
]
∗
c
[
v
]
∗
C
n
u
m
2
\sum_{u=1}^{n}\sum_{v=1}^{n}c[u]*c[v]*C_{num}^{2}
∑u=1n∑v=1nc[u]∗c[v]∗Cnum2
其中num是满足
u
∣
i
u|i
u∣i&&
v
∣
p
[
i
]
v|p[i]
v∣p[i] 的数量, 在考虑容斥如果你算了
u
=
a
∗
b
u = a*b
u=a∗b 的话，那么
a
2
∗
b
a^2*b
a2∗b 也被算了，但如果你算了
u
=
a
，
u
=
b
u = a，u = b
u=a，u=b 的话
u
=
a
∗
b
u = a*b
u=a∗b被多算了，然后题解就给了个式子，如果u 可以表示乘不同的质数的乘积的话那么他是有效的，并且如果他是奇数个质数的乘积的话是要加上的，偶数个质数的乘积的话是要减去的，v的话同理
上面都是前情提要下面是化简部分不化简得话是n2 的，思路就是那个对固定的u来说v只有是不同的质数的乘积的话才有效，不同的质数对
p
[
i
]
p[i]
p[i] 来说，v的个数就很小了，至多63个，那么可以对每个
p
[
i
]
p[i]
p[i]求出可以整除的v。下来再进行计算，没看懂看看代码吧。
int p[N];
vector<int>v[N];
int c[N], num[N];
int main()
{
int n;
scanf("%d", &n);
for(int i = 1;i <= n;i ++) scanf("%d", p+i);
for(int i = 2;i <= n;i ++) // 这个for 是干 求出 c[u] 和每个p[i] 可以整除的v的 ;
{
int a[10], idx = 0, t = i, flag = 1;
for(int x = 2;x <= t/x;x ++)
if(t%x == 0)
{
t /= x;
while(t%x == 0) flag = 0, t /= x;
a[idx++] = x;
}
if(t != 1) a[idx++] = t;
c[i] = flag ? (idx%2 ? 1 : -1) : 0; // flag = 0 代表不是不同的质数的乘积。
for(int _ = 1, m = 1;_ < 1<<idx;v[i].push_back(m), m = 1, _ ++) // 枚举质数的选择，v[i]保存对应的可整除的v；
for(int j = 0;j < idx;j ++)
if(_>>j&1)
m *= a[j];
}
LL ans = 0;
for(int i = 2;i <= n;i ++)
{
if(!c[i]) continue;
debug语句
// cout<<i<<" ++ "<<endl;
for(int j = i;j <= n;j += i)
for(auto x : v[p[j]])
num[x] ++;
for(int j = i;j <= n;j += i)
for(auto x : v[p[j]])
if(num[x])
ans += (LL)c[i]*c[x]*num[x]*(num[x]-1)/2, num[x] = 0;
debug语句
// cout<<x<<' '<<num[x]<<' '<<c[i]<<' '<<c[x]<<endl,
}
ans += p[1] == 1 ? n-1 : n-2; // 还有自己和自己 上面的都是C(n,2), 是不同的数的选择，
cout<<ans<<endl;
return 0;
}