Reincarnation

正因为梦易碎，才格外美好。

P9148 除法题

发表于 更新于 分类于
本文字数： 3.4k 阅读时长 ≈ 3 分钟

被薄纱。

题目简介

题目名称： 除法题

题目来源：

评测链接：https://www.luogu.com.cn/problem/P9148

形式化题意：给定 个两两不同数 ，求 ，对 取模。

数据范围：

显然地，只有当 时，答案有效。所以首先按从小到大排序。

运用一点莫反的思想，转枚举因数为枚举倍数，用 的时间去枚举 ，想方设法得到 ，枚举 的倍数 ，预处理出所有 的 的 ，这个可以在 预处理完成。然后就可以在 的时间内解决这个问题了。

std 还有另外一种方法，枚举 ，并枚举 作为 的倍数，然后用上述同样的方法处理出二位前缀和进行计算即可。已知 ，所以时间复杂度是 。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// ----- Eternally question-----
// Problem: P9148 除法题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9148
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// Written by: Eternity
// Time: 2023-03-12 14:30:45
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
typedef unsigned int ui;
const int MAXN=5e3+10;
int N,M,a[MAXN];
int Rst[MAXN][MAXN];
ui ans,Pre[MAXN][MAXN];
inline bool cmp(int a,int b)
{ return a>b; }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]),checkMax(M,a[i]);
	std::sort(a+1,a+N+1,cmp);
	for(int i=1;i<=N;++i)
		for(int j=1;j<=N;++j) Pre[j][i]=Pre[j][i-1]+a[i]/a[j];
	for(int i=N;i>=1;--i)
	{
		int pos=N;
		for(int s=1;s*a[i]<=M;++s)
		{
			while(pos&&s*a[i]>a[pos]) --pos;
			Rst[i][s]=pos;
		}
		Rst[i][0]=N;
	}
	// for(int i=1;i<=N;++i,puts(""))
		// for(int j=1;j<=N;++j) write(Pre[i][j],' ');
	// for(int i=1;i<=N;++i)
		// for(int s=0;s*a[i]<=M;++s)
			// printf("a[i]:%d %d:%d to %d\n",a[i],s,Rst[i][s+1],Rst[i][s]);
	for(int j=2;j<=N;++j)
		for(int k=j+1;k<=N;++k)
			for(int s=a[j-1]/a[k];s*a[k]<=M;++s)
				ans+=(a[j]/a[k])*s*(Pre[j][std::min(j-1,Rst[k][s])]-Pre[j][Rst[k][s+1]]);
	write(ans);
	return 0;
}
/*

*/
相关文章