2020-2021:teams:wangzai_milk:20200801比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:20200801比赛记录 [2020/08/05 21:12] infinity37 [C - A National Pandemic] |
2020-2021:teams:wangzai_milk:20200801比赛记录 [2020/08/05 21:19] (当前版本) infinity37 [D - Fake News] |
||
|---|---|---|---|
| 行 225: | 行 225: | ||
| 满足 $1$ 到 $n$ 的平方和是完全平方数的只有 $1$ 和 $24$ ，打表之后可以猜得到。 | 满足 $1$ 到 $n$ 的平方和是完全平方数的只有 $1$ 和 $24$ ，打表之后可以猜得到。 | ||
| + | |||
| + | ===== H - Dividing ===== | ||
| + | 经过一顿推导之后可以发现对于同一个$k$，可能的$n$只有$k$的倍数和$k$的倍数$+1$，（包括1），所以要求的就是下面这个式子 | ||
| + | |||
| + | $N+\sum_{i=2}^{K}\lfloor \frac{N}{i}\rfloor +\lfloor\frac{N+1}{i}\rfloor+1$ | ||
| + | |||
| + | 此公式针对$K\leq N$的情况，如果$K>N$，可以使$K=N$，最后答案中加$K-N$，因为对于大于$N$的$k$，每个$k$都仅有$1$这个数字可以作为一组。 | ||
| + | |||
| + | 上面这个式子用数论分块可以直接求，另外要注意一些特殊情况。 | ||
| + | |||
| + | <hidden><code c++> | ||
| + | #include <bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | typedef long long ll; | ||
| + | const ll mod = 1e9+7; | ||
| + | ll getans(ll n,ll k) { | ||
| + | ll ans = 0; | ||
| + | for (ll l = 1,r;l<=k;l=r+1) { | ||
| + | r = min(k,n/(n/l)); | ||
| + | ans += (r-l+1)*(n/l)%mod; | ||
| + | ans = ans%mod; | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | ll ans = 0; | ||
| + | ll n,k; | ||
| + | scanf("%lld%lld",&n,&k); | ||
| + | if (k >= n) { | ||
| + | ans += k-n+2; | ||
| + | k = n-1; | ||
| + | } | ||
| + | ans += getans(n,k)+getans(n-1,k)+k-n; | ||
| + | ans = (ans%mod+mod)%mod; | ||
| + | printf("%lld\n",ans); | ||
| + | return 0; | ||
| + | } | ||
| + | </code></hidden> | ||
| + | |||
2020-2021/teams/wangzai_milk/20200801比赛记录.1596633160.txt.gz · 最后更改: 2020/08/05 21:12 由 infinity37
