1789 : 阶乘问题
题目描述:
给定 n, k，求一个最大的整数 m，使得 km 是 n! 的约数
输入描述：
第一行两个正整数 n, k2 ≤ n,k ≤ 109
输出描述:
输出最大的 m
样例输入：
5 2
样例输出：
3
思路：
将k质数分解求出质因子分别有多少个，然后找出n!的阶乘有多少个相同的质因子，选出质因子个数小的即是答案。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
int n,k;
cin>>n>>k;
int l=sqrt(k);
ll re=0,ans=1e18,m=0;
ll p=0;
for(int i=2;i<=l;i++){
// cout<<k<<endl;
p=0;
while(k%i==0){
p++;
k/=i;
}//p记录k里面有多个相同的质因子。
if(p!=0){
ll q=n;
m=0;
while(q>1){
m+=q/i;
q/=i;//m记录阶乘里有多少个相同的质数因子
}
ans=min(ans,m/p);//选取小的作为答案
}
}
if(k!=1){
ll q=n;
m=0;
while(q>1){
m+=q/k;
q/=k;
}
ans=min(ans,m);
}
cout<<ans<<endl;
return 0;
}
总结：
质数分解定理又有了一定的了解。
牛客小白赛 A 无关：
题目描述：
若一个集合A内所有的元素都不是正整数N的因数，则称N与集合A无关。
给出一个含有k个元素的集合A={a1,a2,a3,...,ak}，求区间[L,R]内与A无关的正整数的个数。
保证A内的元素都是素数。
输入描述：
输入数据共两行：
第一行三个正整数L,R,k，意义如“题目描述”。
第二行k个正整数，描述集合A，保证k个正整数两两不相同。
输出描述：
输出数据共一行：
第一行一个正整数表示区间[L,R]内与集合A无关的正整数的个数
输入描述：
1 10 4
2 3 5 7
输出描述：
1
思路：
题意大概是在1-n中找出有多少个数不能整除素数集合里的所有数。我们可以发现找可以整除的数有多少个比较
简单，找这些数要用容斥原理。容斥原理不会可以自行百度，这里还有一个二进制枚举子集的方法
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=100;
int a[maxn];
ll l,r,k;
ll slove(ll p){
ll ans=0;
for(int i=1;i<(1<<k);i++)
{
ll temp=p;
ll f=-1;
for(int j=0;j<k;j++){
if((i>>j)&1==1){
f*=-1;//这是个小技巧可以很方便容斥的计算
temp/=a[j];//找出1-p中多少个数可以整除集合的素数
}
}
ans+=temp*f;//统计出所有的可以整除的数。
}
//cout<<p-ans<<endl;
return p-ans;
}
int main(){
cin>>l>>r>>k;
for(int i=0;i<k;i++){
cin>>a[i];
}
ll ans=0;
ans=slove(r)-slove(l-1);//分别计算出1-r，1-l区间里的答案相减即可。
cout<<ans<<endl;
}
总结：
这个题让我对二进制枚举子集有了更深入的了解，对容斥也有一定的了解。最重要的是自己知道如果要求 1-n里有
多少个数可以整除a，只要用n/a就可以得出答案。
codeforce 499 E
题目链接：
http://codeforces.com/contest/1011/problem/E
思路：
用斐蜀定理即可题意大概是给一列数任意组合对k进制取模的不同个数有多少个
斐蜀定理：任意 x,y,ax+by=gcd(a,b)的倍数，x,y 不同意味不同的组合。多个数一样的，不懂可以百度
所以这道题就变成在1-k内gcd(a1,a2,a3,a4,..,k)的倍数有多个不同。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int gcd(int c,int f){
//cout<<c<<" "<<f<<endl;
if(f==0)
return c;
return gcd(f,c%f);
}
int a[maxn];
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=a[i]%k;
}
int g=k;
// cout<<g<<endl;
for(int i=1;i<=n;i++){
//cout<<g<<" "<<a[i]<<endl;
g=gcd(g,a[i]);
}
vector<int>st;
for(int i=g;i<=k;i+=g){
st.push_back(i%k);
}
sort(st.begin(),st.end());
cout<<st.size()<<endl;
for(auto i:st){
cout<<i<<" ";
}
cout<<endl;
}
总结：
学到了一个定理，同时自己在用定理时无法转化到对应的关键点多谢大佬指点。