请问如此可怕的数论题写错了,查了半个小时,下一步应该怎么办?
  • 板块灌水区
  • 楼主Swiftie_wyc22
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/1/15 21:34
  • 上次更新2023/10/24 04:04:55
查看原帖
请问如此可怕的数论题写错了,查了半个小时,下一步应该怎么办?
285414
Swiftie_wyc22楼主2023/1/15 21:34
#include <bits/stdc++.h>
#define rei register int
#define ll long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, ll mod){long long res = 1;  while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod;  b >>= 1;  }  return res;}

using namespace std;

const ll mod = 19940417, iv2 = 9970209 , iv6 = 3323403;

const ll sm(int l, int r) {
	return (r * (r + 1) % mod * (2 * r + 1) % mod - l * (l - 1) % mod * (2 * l - 1) % mod) % mod * iv6 % mod;
}

int main()
{
	int n, m;
	cin >> n >> m; if (n > m) swap(n, m);
	ll smi1 = 0, smi2 = 0, ans = 0;
	int r;
	for (int l = 1; l <= n; l = r + 1) {
		r = n / (n / l);
		smi1 = (smi1 + (r - l + 1) % mod * (l + r) % mod * iv2 % mod * (r - l + 1) % mod * (n / l) % mod) % mod;
	}
	smi1 = (1ll * n * n - smi1) % mod;
	
	for (int l = 1; l <= m; l = r + 1) {
		r = m / (m / l);
		smi2 = (smi2 + (r - l + 1) % mod * (l + r) % mod * iv2 % mod * (r - l + 1) % mod * (m / l) % mod) % mod;
	}
	smi2 = (1ll * m * m - smi2) % mod;
	ans = (smi1 + smi2) % mod;
	
	
	ans -= 1ll * n * n % mod * m % mod;
	
	ll smi3 = 0;
	for (int l = 1; l <= n; l = r + 1) {
		r = n / (n / l);
		smi3 = (smi3 + m * (r - l + 1) % mod * (r - l + 1) * (l + r) % mod * iv2 % mod + (r - l + 1) * (n / l) % mod) % mod;
	}
	ans = (ans + smi3) % mod;
	
	ll smi4 = 0;
	for (int l = 1; l <= n; l = r + 1) {
		r = n / (n / l);
		smi4 = (smi4 + n * (r - l + 1) % mod * (r - l + 1) * (l + r) % mod * iv2 % mod + (r - l + 1) * (m / l) % mod) % mod;
	}
	ans = (ans + smi4) % mod;
	
	ll smi5 = 0;
	for (int l = 1; l <= n; l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		smi5 = (smi5 + sm(l, r) * (n / l) % mod * (m / l) % mod) % mod;
	}
	ans = (ans - smi5) % mod;
	cout << ans << endl;
    return 0;
}
2023/1/15 21:34
加载中...