fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define nmax 100005
  4.  
  5. typedef long long ll;
  6.  
  7.  
  8. ll m, n, l, r, p, num[nmax], d[nmax][6], ans, ii;
  9.  
  10. ll tt(ll ql, ll qh, ll mm) {
  11. 	qh = qh / mm; ql = (ql + mm - 1) / mm;
  12. 	return ((qh - ql + 1) * (n + 1) - mm * ((qh * (qh + 1) - (ql - 1) * ql) / 2)) % p;
  13. }
  14.  
  15. int main() {
  16.  
  17. 	scanf("%lld%lld", &n, &m);
  18. 	scanf("%lld%lld%lld", &l, &r, &p);
  19.  
  20. 	for(int i = 2; i <= m; i++)
  21. 		if(num[i] == 0)
  22. 			for(int j = i; j <= m; j += i)
  23. 				d[j][num[j]++] = i;
  24.  
  25.     ll lo = l;
  26. 	ll hi = r;
  27.     ll minn = (m < r ? m : r);
  28. 	for(ll w = 1; w <= minn; w++) {
  29. 		while(lo > 1 && l*l - w*w <= (lo-1)*(lo-1))
  30. 			lo--;
  31. 		while(r*r - w*w < hi*hi)
  32. 			hi--;
  33. 		if(lo <= hi && lo <= n) {
  34. 			ll a = 0;
  35. 			int t = (1 << num[w]);
  36. 			for(int i = 0; i < t; i++) {
  37. 				ii = i;
  38. 				ll p1 = 1;
  39. 				ll p2 = 1;
  40. 				for(int j = 0; j < num[w]; j++) {
  41. 					if(ii & 1) {
  42. 						p1 *= d[w][j];
  43. 						p2 *= -1;
  44. 					}
  45. 					ii >>= 1;
  46. 				}
  47. 				a += p2 * tt(lo, hi < n ? hi : n, p1);
  48. 			}
  49. 			ans = (ans + a*(m-w+1)) % p;
  50. 			if(ans < 0) ans += p;
  51. 		}
  52. 	}
  53.  
  54. 	if(l <= 1 && r >= 1) ans = (2 * ans + m * (n + 1) + n * (m + 1)) % p;
  55. 	else ans = (2 * ans) % p;
  56. 	printf("%d\n", ans);
  57. }
Runtime error #stdin #stdout 0s 8816KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HKB2Us
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!