模拟赛里的题，但是没有做出来...有点菜啊。
题目链接
题意
一个人买了
中的若干个皮肤，皮肤编号的最大公倍数为 ，最小公约数为 。
现在给出
组询问，每次询问有多少种方案买了皮肤 。
。
。
。
题解
首先我们可以做一步非常简单的转化，让我们之后的步骤更顺手。
显然，所有可能买的皮肤肯定都是
的倍数，询问的 肯定只在为 的倍数时才有答案。
所以我们可以先把
和所有询问都先除以 ，这样我们就可以把 当作 来处理。
当然，一个小坑点，要特判一下
是不是 的倍数。
然后我们在来想一下有什么皮肤可能会在方案中，显然只有
的因数。
容易注意到一个点， 最大范围是
，而 以内因数最多数字，因数只有 个。
这提示我们可以先预处理出
因数的答案，然后询问时直接输出即可。
现在我们可以来想一想，有多少种方案包含皮肤 ，并且皮肤编号的最大公约数是 ，最小公倍数是 。
我在模拟赛时想到的思路就是容斥。
容斥
不难看出，这道题有两个条件需要满足。
条件一为皮肤的最大公约数是 ，转化一下，可以得到若干个条件，形如：
至少有一个皮肤的编号不是
的倍数，其中 。
条件二为皮肤的最小公倍数是 ，转化一下，可以得到若干个条件，形如：
至少有一个皮肤的编号是
的倍数，其中 。
其中
已经满足的条件可以去掉。
这样子，我们就可以暴力枚举哪些条件不满足，进行容斥。
如果条件一不满足，那么他就会长这个样子：
没有皮肤的编号不是
的倍数，也就是说所有皮肤编号都是
的倍数， 的定义如上。
如果条件二不满足，那么他就会长这个样子：
没有皮肤的编号是 的倍数， 的定义如上。
然后我们暴力枚举每一个条件是否不满足，然后暴力枚举每一个可能的皮肤，直接容斥。
看一个皮肤满不满足一个条件可以通过提前预处理，然后 使用位运算回答。
时间复杂度为 。
打表可得，在 取 时这个数字最大，可以达到 。
时限是 ，可过。
打表程序核心代码放上，我本机差不多跑了半分钟。
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
| int main()
{
for(int i=2;i<=n;i++)
{
if(!is[i]) pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<=n;j++)
{
is[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
for(int i=1;i<=n;i++) for(int j=1;i*j<=n;j++) num[i*j]++;
for(int i=1;i<=n;i++) num[i]*=num[i];
for(int i=1;i<=pri[0];i++) for(int j=1;pri[i]*j<=n;j++)
{
num[pri[i]*j]<<=1;
if(j%pri[i]==0) num[pri[i]*j]<<=1;
}
int ans=0;
for(int i=1;i<=n;i++)
{
if(num[i]>num[ans]) ans=i;
}
printf("%d : %lld\n",ans,num[ans]);
return 0;
}
|
算条件个数的地方可能不太好理解。
代码
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int mod=1000000007;
using ll=long long;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
map<int,ll>ans;
ll p[1048576];
int pop[1048576];
bool is[10001];
int pri[10001];
int a[100001];
int visx[10001];
int visy[10001];
int x[20];
int y[20];
int n,G,L,Q;
int tot;
inline void run(int num)
{
int val=num/G;x[0]=y[0]=0;
for(int i=1;pri[i]*pri[i]<=val&&i<=pri[0];i++) if(val%pri[i]==0)
{
x[++x[0]]=pri[i];
while(val%pri[i]==0) val/=pri[i];
}
if(val!=1) x[++x[0]]=val;
val=L;
for(int i=1;pri[i]*pri[i]<=val&&i<=pri[0];i++) if(val%pri[i]==0)
{
int v=1;
while(val%pri[i]==0) val/=pri[i],v*=pri[i];
if(num%v) y[++y[0]]=v;
}
if(val!=1&&num%val) y[++y[0]]=val;
for(int i=1;i<=tot;i++)
{
visx[i]=visy[i]=0;
for(int j=1;j<=x[0];j++) if(a[i]%x[j]) visx[i]|=(1<<(j-1));
for(int j=1;j<=y[0];j++) if(a[i]%y[j]==0) visy[i]|=(1<<(j-1));
}
ll va=0;
for(int i=0;i<(1<<x[0]);i++) for(int j=0;j<(1<<y[0]);j++)
{
int sum=0;
for(int k=1;k<=tot;k++) if(a[k]!=num) sum+=(!(visx[k]&i)&&!(visy[k]&j));
int flag=(pop[i]+pop[j])&1?-1:1;
va+=flag*p[sum];
}
ans[num]=(va%mod+mod)%mod;
}
int main()
{
p[0]=1;
for(int i=1;i<1048576;i++) pop[i]=pop[i-(i&(-i))]+1,p[i]=p[i-1]*2%mod;
for(int i=2;i<=10000;i++)
{
if(!is[i]) pri[++pri[0]]=i,is[i]=1;
for(int j=1;j<=pri[0]&&i*pri[j]<=10000;j++)
{
is[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
n=read(),G=read(),L=read(),Q=read();
if(L%G)
{
for(int i=1;i<=Q;i++) printf("0\n");
return 0;
}
int memG=G;L/=G,n/=G,G=1;
for(int i=1;i<=n&&i*i<=L;i++) if(L%i==0)
{
a[++tot]=i;
if(i!=L/i&&L/i<=n) a[++tot]=L/i;
}
for(int i=1;i<=tot;i++) run(a[i]);
for(int i=1;i<=Q;i++)
{
int x=read();
if(x%memG||!ans.count(x/memG)) printf("0\n");
else printf("%lld\n",ans[x/memG]);
}
return 0;
}
|
你谷上开 O2 最大点跑了 。
感谢观看！