首页 > 代码库 > 【bzoj2956】模积和 数论+分块
【bzoj2956】模积和 数论+分块
题目描述
求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。
输入
第一行两个数n,m。
输出
一个整数表示答案mod 19940417的值
样例输入
3 4
样例输出
1
题解
数论+分块
由于直接求i≠j的情况比较难搞，所以我们可以先求出i可以等于j的和，然后再减去i等于j时的情况。
也就是求∑∑((n mod i)*(m mod j))-∑((n mod i)*(m mod i))。
然后再根据乘法分配律转化为∑(n mod i)*∑(m mod i)-∑((n mod i)*(m mod i))。
因为有n mod i = n-(n/i)*i（这里的除号均表示向下取整）。
所以∑(n mod i) = ∑(n-(n/i)*i) = n*n-∑((n/i)*i)。
这里n/i最多只有√n 种取值，我们可以分块来求，这里用到1,2,3,...,n的和。
后面一坨变为∑((n-(n/i)*i)*(m-(m/i)*i))=∑(nm-m*(n/i)*i-n/(m/i)*i+(n/i)*(m/i)*i^2)。
同样的方法处理，运用一下1^2,2^2,3^2,...,n^2的和。
最后减一下即可。
然而有一个问题，就是套用公式的时候需要除法，不能先取模，而不先取模还会爆long long。
好在除的数是固定的2和6，于是可以直接把mod开大6倍，最后再模回去即可。
#include <cstdio>
#include <algorithm>
#define MOD 119642502
using namespace std;
typedef long long ll;
ll sum1(ll p)
{
return p * (p + 1) % MOD / 2;
}
ll sum2(ll p)
{
return p * (p + 1) % MOD * (2 * p + 1) % MOD / 6;
}
ll calc1(ll n)
{
ll ans = n * n % MOD , i , last = 0;
for(i = 1 ; i <= n ; i = last + 1)
{
last = n / (n / i);
ans = (ans - (n / i) % MOD * (sum1(last) - sum1(i - 1) + MOD) % MOD + MOD) % MOD;
}
return ans;
}
ll calc2(ll n , ll m)
{
ll ans = n * m % MOD * min(n , m) % MOD , i , last = 0;
for(i = 1 ; i <= n && i <= m ; i = last + 1)
{
last = min(n / (n / i) , m / (m / i));
ans = (ans - m * (n / i) % MOD * (sum1(last) - sum1(i - 1) + MOD) % MOD
- n * (m / i) % MOD * (sum1(last) - sum1(i - 1) + MOD) % MOD
+ (n / i) * (m / i) % MOD * (sum2(last) - sum2(i - 1) + MOD) % MOD + 2 * MOD) % MOD;
}
return ans;
}
int main()
{
ll n , m;
scanf("%lld%lld" , &n , &m);
printf("%lld\n" , (calc1(n) * calc1(m) % MOD - calc2(n , m) + MOD) % (MOD / 6));
return 0;
}
【bzoj2956】模积和 数论+分块
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。