Problem Description:
铁头娃制作了很多蛋糕,想分给他的小伙伴们,他的小伙伴很喜欢铁头娃做的蛋糕,每个人都想分到最多蛋糕
铁头娃想到了一个头铁主意:先给小伙伴们从1到N编号,在1-N区间随机选择一个数字K,每个编号取余K等于0的小伙伴会分
到一个蛋糕,重复多次,分蛋糕的过程有时铁头娃想皮一下,就会随机选择一个编号D的小伙伴,问他分到了多少块蛋糕。
Input:
输入数据有多组,每一组第一行包含两个数字N,M(1 <= N <= 50000 , 1 <= M <= 50000)
接下来M行,每一行包含两个数,
第一个数输入1则表示铁头娃要分蛋糕,接下来一个数字K,表示所有编号取余K为0的小伙伴分到一个蛋糕。
第一个数如果是2,表示铁头娃想皮一下,接下来一个数字D。
Output:
对于每次铁头娃的皮,输出D号小伙伴拥有的蛋糕
Sample Input:
5 5
1 1
1 3
1 4
2 2
2 3
Sample Output:
1
2
解题思路:刚开始做这道题时,不知道怎么把因子k的倍数的个数依次加1,(菜鸡弱,做题少,想不出来QAQ,生硬暴力结果TLE,流下了没技术的眼泪Orz)。当看到这个题解时恍然大悟,原来可以这么做。做法:定义一个一维数组,其元素类型是vector容器,用来存放每个数组元素下标的所有因子。再定义一个一维数组用来存放每个数被标记的次数。这里要转换一下求解思路:把分蛋糕看做是数字出现的次数,每次取编号k仅将其次数加1,当访问编号D元素分到多少个蛋糕时,只需将D中每个因子的个数加起来即为编号D分到蛋糕的个数,这样就大大降低了时间复杂度。
AC代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
vector<int> vec[maxn];//把数组中每一个元素定义为vector容器,存放的是对应下标的所有因子
void init(){
for(int i=;i<maxn;++i)vec[i].clear();
vec[].push_back();//1的因子只有1
for(int i=;i<=;++i){
vec[i].push_back();
vec[i].push_back(i);//包括1和它本身的因子先放进容器
}
for(int i=;i<=;++i)//i是j的因子
for(int j=i*;j<=maxn;j+=i)//i的倍数即为j的因子
vec[j].push_back(i);
}
int n,m,x,y,cnt[maxn];//数组cnt记录每个因子的个数
int main(){
init();//打表
while(cin>>n>>m){
memset(cnt,,sizeof(cnt));//初始化
while(m--){
cin>>x>>y;
if(x==)cnt[y]++;//将y这个因子的个数加1
else{
int ans=;
for(size_t i=;i<vec[y].size();++i)
ans+=cnt[vec[y][i]];//将D中每个因子的个数全部加起来
cout<<ans<<endl;
}
}
}
return ;
}