之零:
这一篇都是水题,不过还是有几道被卡了一下,还是总结一下。
A题:
给定a和b的gcd和lcm,求一组满足的a,b,且a最小。
显然,a,b必然是gcd的倍数,是lcm的约数,如果gcd不是lcm的约数则无解,否则,要使a最小,a只能是gcd,又因为b是gcd的倍数,那么b就只能是a的倍数,也就只能是a和b的最小公倍数lcm,所以答案就是a=gcd,b=lcm。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll G,L;
int main()
{
//freopen("in.txt","r",stdin);
int T;cin>>T;
while(T--){
scanf("%lld%lld",&G,&L);
if(L%G==0) printf("%lld %lldn",G,L);
else puts("-1");
}
return 0;
}
View Code
B题:
给定A,C,且LCM(A,B)=C,求满足等式的最小的B。
因为lcm=...p^k=...p^max(k1,k2),对C和A分别质因数分解,要使B最小,那么如果某个质因数p在C中出现的次数大于A的次数,那么B必须去C的次数,否则不取该质因数。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll a,b,c;
bool isprime[maxn];
vector<int> prime;
void getPrime()
{
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
REP(i,2,maxn-1){
if(!isprime[i]) continue;
for(int j=i+i;j<maxn;j+=i) isprime[j]=0;
}
REP(i,2,maxn-1) if(isprime[i]) prime.push_back(i);
}
ll qpow(ll n,ll k)
{
ll res=1;
while(k){
if(k&1) res*=n;
n*=n;
k>>=1;
}
return res;
}
ll solve()
{
ll res=1;
ll A=a,C=c;
for(int i=0;i<prime.size();i++){
ll t=prime[i];
if(t*t>C) break;
int cntA=0,cntC=0;
while(A%t==0) cntA++,A/=t;
while(C%t==0) cntC++,C/=t;
if(cntA<cntC) res*=qpow(t,cntC);
}
if(C!=1&&A==1) res*=C;
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
getPrime();
int T;cin>>T;
while(T--){
scanf("%lld%lld",&a,&c);
if(c%a) puts("NO SOLUTION");
else printf("%lldn",solve());
}
return 0;
}
View Code
C题:
把一个数N分成k个数的和,问方案数。
问题等价于x1+x2+...+xk=N. (0<=xi<=N).
另y=x+1,则y1+y2+...+yk=N+k,然后隔板即可得到C(N+k-1,k-1)。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll n,k;
ll C[1200][1200];
void Init()
{
C[0][0]=1;
REP(i,1,1100){
REP(j,0,i){
if(j==0) C[i][j]=C[i-1][j];
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%1000000;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
Init();
while(~scanf("%lld%lld",&n,&k)){
if(n==0&&k==0) break;
printf("%lldn",C[n+k-1][k-1]);
}
return 0;
}
View Code
D题:
找最大的k使 m^k能整除n!。
对n!和m进行质因数分解,记下每个质因数的次数。二分k,判断m^k能否整除n!,能整除的条件是所有质因数都满足次数大于等于另一个,k次方只要将次数乘以k即可。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll p1[maxn],cnt1[maxn];
ll p2[maxn],cnt2[maxn];
int pn;
ll n,m;
vector<int> prime;
bool isprime[maxn];
void getPrime()
{
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
REP(i,2,maxn-1){
if(!isprime[i]) continue;
for(int j=i+i;j<maxn;j+=i) isprime[j]=0;
}
REP(i,2,maxn-1) if(isprime[i]) prime.push_back(i);
}
void get(ll n,ll m)
{
pn=0;
for(int i=0;i<prime.size();i++){
ll t=prime[i];
if(t>10000) break;
p1[++pn]=t;cnt1[pn]=0;
p2[pn]=t;cnt2[pn]=0;
while(m%t==0) cnt2[pn]++,m/=t;
}
REP(i,1,n){
ll x=i;
REP(j,1,pn){
ll t=p1[j];
if(t>x) break;
while(x%t==0) cnt1[j]++,x/=t;
}
}
}
bool check(ll k)
{
REP(i,1,pn){
if(cnt1[i]<cnt2[i]*k) return 0;
}
return 1;
}
ll bin(ll l,ll r)
{
ll res=-1;
while(l<=r){
ll m=(l+r)>>1;
if(check(m)) l=m+1,res=m;
else r=m-1;
}
return res;
}
void solve()
{
ll ans=bin(1,INF);
if(ans==-1) puts("Impossible to divide");
else printf("%lldn",ans);
}
int main()
{
//freopen("in.txt","r",stdin);
getPrime();
int T;cin>>T;int casen=1;
while(T--){
scanf("%lld%lld",&m,&n);
get(n,m);
printf("Case %d:n",casen++);
solve();
}
return 0;
}
View Code
E题:
求有多少对(a,b)满足lcm(a,b)=n,a<=b。
对n进行质因数分解,由于lcm=...p^k=p^max(ka,kb),所以每个质因子的方案数就是2*(k+1)-1,然后乘法原理连乘,得到cnt,但这会多算a>b的,所以答案就是(cnt-1)/2+1,1是a=b的情况。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll n;
ll p[maxn],pn;
ll cnt[maxn];
vector<int> prime;
bool isprime[maxn];
void getPrime()
{
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
REP(i,2,maxn-1){
if(!isprime[i]) continue;
for(int j=i+i;j<maxn;j+=i) isprime[j]=0;
}
REP(i,2,maxn-1) if(isprime[i]) prime.push_back(i);
}
void get(ll n)
{
pn=0;
for(int i=0;i<prime.size();i++){
ll t=prime[i];
if(t*t>n) break;
if(n%t==0){
p[++pn]=t;cnt[pn]=0;
while(n%t==0) cnt[pn]++,n/=t;
}
}
if(n!=1) p[++pn]=n,cnt[pn]=1;
}
ll solve()
{
get(n);
ll res=1;
REP(i,1,pn) res*=(2*(cnt[i]+1)-1);
return (res+1)/2;
}
int main()
{
//freopen("in.txt","r",stdin);
getPrime();
while(~scanf("%lld",&n)&&n){
printf("%lld %lldn",n,solve());
}
return 0;
}
View Code
F题:
打印1~2^64-1范围内的超级幂(即满足是两个数以上的幂的数).
显然,超级幂等价于某个数的合数次幂,幂次的最大值肯定在64以内,所以只需要找出64之内的合数,最小的合数是4,所以底数最大是2^16,枚举即可,用取对数转double判断是否超过2^64-1。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned long long ll;
const int maxn=1000100;
const int INF=1e9+10;
const double EPS=1e-10;
vector<int> prime;
bool isprime[maxn];
void getPrime()
{
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
REP(i,2,maxn-1){
if(!isprime[i]) continue;
for(int j=i+i;j<maxn;j+=i) isprime[j]=0;
}
REP(i,2,maxn-1) if(isprime[i]) prime.push_back(i);
}
set<ll> ans;
void work(ll p)
{
ll cur=p;
REP(i,2,65){
if(1.0*cur*p>pow(2.0,64.0)-1.0+EPS) return;
ll t=cur*p;
if(t/p!=cur) return;
cur*=p;
if(cur<=0) return;
if(isprime[i]) continue;
ans.insert(cur);
}
}
void solve()
{
ans.clear();
REP(i,2,(1LL<<16)) work(i);
}
int main()
{
//freopen("in.txt","r",stdin);
getPrime();
solve();
printf("1n");
for(set<ll>::iterator it=ans.begin();it!=ans.end();++it) printf("%llun",*it);
//cout<<(int)ans.size()<<endl;
return 0;
}
View Code
G题:
求一个数列的所有排列组成的n位数的和。
显然每一位的和都是一样的,容易算出排列的个数为Cnt=n!/(cnt1!cnt2!...cntk!) ,那么每一位的数的和就是Cnt序列平均数=Cnt*sum/n。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned long long ll;
const int maxn=1000100;
const int INF=1e9+10;
int n;
ll a[maxn];
ll fac[maxn];
map<ll,ll> cnt;
void Init()
{
fac[0]=1;
REP(i,1,12) fac[i]=fac[i-1]*i;
}
int main()
{
//freopen("in.txt","r",stdin);
Init();
while(~scanf("%d",&n)&&n){
ll s=0;cnt.clear();
REP(i,1,n) scanf("%llu",&a[i]),s+=a[i],cnt[a[i]]++;
ll Cnt=fac[n];
for(map<ll,ll>::iterator it=cnt.begin();it!=cnt.end();++it) Cnt/=fac[it->second];
s*=Cnt;
s/=n;
ll res=0;
REP(i,1,n) res=res*10+s;
printf("%llun",res);
}
return 0;
}
View Code
H题:
求n个人,去k个人组成一只队伍,并从k个人中选一个队长的方案数(1<=k<=n),k可以任取,没有给定。
显然答案等于C(n,1)1+C(n,2)2+...+C(n,n)*n.
kC(n,k)=kn!/(k!(n-k)!)=n(n-1)!/((k-1)!((n-1)-(k-1))!)=nC(n-1,k-1).
则C(n,1)1+C(n,2)2+...+C(n,n)n= n( C(n-1,0)+C(n-1,1)+...+C(n-1,n-1)) = n*(2^(n-1) -1) .
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned long long ll;
const int maxn=1000100;
const int INF=1e9+10;
const ll MOD=1e9+7;
ll n;
ll qpow(ll n,ll k,ll p)
{
ll res=1;
while(k){
if(k&1) res=(res*n)%p;
n=(n*n)%p;
k>>=1;
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
int T;cin>>T;int casen=1;
while(T--){
scanf("%lld",&n);
printf("Case #%d: %lldn",casen++,(n*qpow(2,n-1,MOD))%MOD);
}
return 0;
}
View Code
I题:
求第n个回文数。
很容易算出长度为len的回文数的个数为f(len).
先确定第n个回文数的长度,然后保证首位大于0,按字典序逐个放置即可。
确实是略麻烦,需要细心一点。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll n;
int ans[maxn];
ll qpow(ll n,ll k)
{
ll res=1;
while(k){
if(k&1) res*=n;
n*=n;
k>>=1;
}
return res;
}
ll Cnt(int len)
{
if(len==0) return 0;
if(len%2==0) return qpow(10,len/2-1)*9;
else return qpow(10,len/2)*9;
}
void solve(ll n)
{
int len;
REP(i,1,20){
ll t=Cnt(i);
if(t>=n){
len=i;break;
}
n-=t;
}
if(len%2==0){
if(len==2) ans[1]=ans[2]=n;
else{
ans[1]=(n-1)/qpow(10,len/2-1)+1;
n=(n-1)%qpow(10,len/2-1);
for(int i=len/2;i>=2;i--) ans[i]=n%10,n/=10;
REP(i,len/2+1,len) ans[i]=ans[len+1-i];
}
}
else{
if(len==1) ans[1]=n;
else{
ans[1]=(n-1)/qpow(10,len/2)+1;
n=(n-1)%qpow(10,len/2);
for(int i=len/2+1;i>=2;i--) ans[i]=n%10,n/=10;
REP(i,len/2+1,len) ans[i]=ans[len+1-i];
}
}
REP(i,1,len) printf("%d",ans[i]);puts("");
}
void test()
{
REP(i,1,300) solve(i);
}
int main()
{
//freopen("in.txt","r",stdin);
//test();return 0;
while(~scanf("%lld",&n)&&n){
solve(n);
}
return 0;
}
View Code
J题:
给一堆数,A,B轮流操作,每次操作任取走一个数,使剩下的数的和能被3整除,不能操作者为输,判断胜者。
直接取走一个%3=k的数和取走另一个同样%3=k的数是等价的,模拟即可。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
int cnt[3];
char s[maxn];
int len;
bool dfs(int len,int sum,int x,int y,int z)
{
if(len==1) return 1;
if(sum==0){
if(x>0) return !dfs(len-1,0,x-1,y,z);
return 0;
}
if(sum==1){
if(y>0) return !dfs(len-1,0,x,y-1,z);
return 0;
}
if(sum==2){
if(z>0) return !dfs(len-1,0,x,y,z-1);
return 0;
}
}
int main()
{
//freopen("in.txt","r",stdin);
int T;cin>>T;int casen=1;
while(T--){
printf("Case %d: ",casen++);
scanf("%s",s+1);
len=strlen(s+1);
MS0(cnt);
int sum=0;
REP(i,1,len) cnt[(s[i]-'0')%3]++,sum+=s[i]-'0';
if(dfs(len,sum%3,cnt[0],cnt[1],cnt[2])) puts("S");
else puts("T");
}
return 0;
}
View Code
K题:
把一个数N分解成几个数的lcm,使LCM(a1,a2,...,ak)=N,求最小的a1+a2+...+ak.
显然分解成不互质且每个ai尽量小就好,那么质因数分解即可,答案就是ans=p1^k1+p2^k2+...+pm^km.
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
ll n;
vector<int> prime;
bool isprime[maxn];
void getPrime()
{
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
REP(i,2,maxn-1){
if(!isprime[i]) continue;
for(int j=i+i;j<maxn;j+=i) isprime[j]=0;
}
REP(i,2,maxn-1) if(isprime[i]) prime.push_back(i);
}
ll qpow(ll n,ll k)
{
ll res=1;
while(k){
if(k&1) res*=n;
n*=n;
k>>=1;
}
return res;
}
ll solve()
{
if(n==1) return 2;
ll pn=0;
ll res=0;
for(int i=0;i<prime.size();i++){
ll t=prime[i];
if(t*t>n) break;
if(n%t==0){
ll cnt=0;
while(n%t==0) n/=t,cnt++;
res+=qpow(t,cnt);
pn++;
}
}
if(n!=1){
res+=n;
pn++;
}
if(pn==1) res++;
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
int casen=1;getPrime();
while(~scanf("%lld",&n)&&n){
printf("Case %d: ",casen++);
printf("%lldn",solve());
}
return 0;
}
View Code
L题:
求a和b之间的平方数个数1<=a<=b<=1e6,范围比较小,暴力即可,水题。
如果范围1e18的话,可能数位dp可解。
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1000100;
const int INF=1e9+10;
int L,R;
int F(int n)
{
int res=0;
REP(i,1,n){
if(i*i>n) break;
res++;
}
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%d%d",&L,&R)){
if(L==0&&R==0) break;
printf("%dn",F(R)-F(L-1));
}
return 0;
}
View Code
原文链接: https://www.cnblogs.com/--560/p/5407581.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/232162
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!