D31
Ekka Dokka
Description:Ekka Dokka
Ekka and his friend Dokka decided to buy a cake. They both love cakes and that's why they want to share the cake after buying it. As the name suggested that Ekka is very fond of odd numbers and Dokka is very fond of even numbers, they want to divide the cake such that Ekka gets a share of N square centimeters and Dokka gets a share of M square centimeters where N is odd and M is even. Both N and M are positive integers.
They want to divide the cake such that N * M = W, where W is the dashing factor set by them. Now you know their dashing factor, you have to find whether they can buy the desired cake or not.
Input
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case contains an integer W (2 ≤ W < 2^63). And W will not be a power of 2.
Output
For each case, print the case number first. After that print "Impossible" if they can't buy their desired cake. If they can buy such a cake, you have to print N and M. If there are multiple solutions, then print the result where M is as small as possible.
Sample Input
3
10
5
12
Sample Output
Case 1: 5 2
Case 2: Impossible
Case 3: 3 4
Problem solving:
这道题跟前几天讲质因数分解的时候的一道题一模一样，就不说了。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n;
ll a;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
ll ans=1;
if(a%2==1)
{
printf("Case %d: Impossible\n", i);
continue;
}
while(a%2==0)
{
a/=2;
ans*=2;
}
printf("Case %d: %lld %lld\n",i,a,ans);
}
}How many integers can you find
Description:
Now you get a number N, and a M-integers set, you should find out how many integers which are small than N, that they can divided exactly by any integers in the set. For example, N=12, and M-integer set is {2,3}, so there is another set {2,3,4,6,8,9,10}, all the integers of the set can be divided exactly by 2 or 3. As a result, you just output the number 7.
Input
There are a lot of cases. For each case, the first line contains two integers N and M. The follow line contains the M integers, and all of them are different from each other. 0<N<2^31,0<M<=10, and the M integer are non-negative and won’t exceed 20.
Output
For each case, output the number.
Sample Input
12 2
2 3
Sample Output
7
Problem solving:
这道题的意思是先输入两个数，一个是代表需要查询的范围。一个是某数组的大小（数的个数）。问你在查询的范围内，有多少数是可以只被给的数组中的数整除。
这道题用到了二进制枚举和容斥定理。
用二进制枚举得出每一个状态，然后用到容斥定理的奇加偶减，有一个需要注意的地方就是容斥定理算的时候，总范围除以的是两个数的lcm而不是直接相除。这个应该还挺好理解的，因为两个数相乘不一定是两个数的lcm。
lcm = 最小公倍数
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[21];
ll lcm(ll x,ll y)
{
return x*y/__gcd(x,y);
}
int main()
{
while(cin>>n>>m)
{
int pos=0;
for(int i=0;i<m;i++)
{
cin>>a[pos];
if(a[pos]) pos++;
}
ll sum=0;
for(int i=1;i<(1<<pos);i++)
{
ll res=1,tot=0;
for(int j=0;j<pos;j++)
{
if(i&(1<<j))
{
res=lcm(res,a[j]);
tot++;
}
}
if(tot&1) sum+=(n-1)/res;
else sum-=(n-1)/res;
}
cout<<sum<<endl;
}
} Co-prime
Description:
Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.
Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.
Input
The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1e15) and (1 <=N <= 1e9).
Output
For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.
Sample Input
2
1 10 2
3 15 5
Sample Output
Case #1: 5
Case #2: 10
Hint
In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.
Problem solving:
这道题的意思就是给了你一个区间，让你求区间内与另一个数互质的数有多少。
用到的有容斥定理，质因子分解和二进制枚举。
假设让我们找的是与n互质的数，那我们找到与n互质的然后用总个数减去这个数就是互质的数了。怎么求互质的数呢，我们可以先求出n的每个质因子。然后用容斥定理求出互质的数的总个数。容斥定理：奇加偶减。
还有一点就是这个题他不是从一开始的区间，他是从a到b，计算的时候同时计算a-1区间内的和b区间内的，最后相减即可。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n,t,a,b;
ll p[105];
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a>>b>>t;
memset(p,0,sizeof(p));
ll pos=0;
for(int i=2;i*i<=t;i++)
{
if(t%i==0) pos++,p[pos]=i;
while(t%i==0) t/=i;
}
if(t!=1) pos++,p[pos]=t;
ll ans=0;
for(int i=1;i<(1<<pos);i++)
{
ll mid=0,miid=1;
for(int j=0;j<pos;j++)
{
if(1&(i>>j))
{
mid++;
miid*=p[j+1];
}
}
if(mid%2==1)
{
ans+=b/miid;
ans-=(a-1)/miid;//这里就是因为我们计算的是a到b的，所以得减去a-1之内的
}
else
{
ans-=b/miid;
ans+=(a-1)/miid;//与上面同理
}
}
printf("Case #%d: %lld\n",i,b-a+1-ans);
}
} Find a multiple
Description:
The input contains N natural (i.e. positive integer) numbers ( N <= 10000 ). Each of that numbers is not greater than 15000. This numbers are not necessarily different (so it may happen that two or more of them will be equal). Your task is to choose a few of given numbers ( 1 <= few <= N ) so that the sum of chosen numbers is multiple for N (i.e. N * k = (sum of chosen numbers) for some natural number k).
Input
The first line of the input contains the single number N. Each of next N lines contains one number from the given set.
Output
In case your program decides that the target set of numbers can not be found it should print to the output the single number 0. Otherwise it should print the number of the chosen numbers in the first line followed by the chosen numbers themselves (on a separate line each) in arbitrary order.
If there are more than one set of numbers with required properties you should print to the output only one (preferably your favorite) of them.
Sample Input
5
1
2
3
4
1
Sample Output
2
2
3
Problem solving:
这道题用到的是鸽巢原理。
还是去看学长的题解吧：https://blog.csdn.net/qq_42757965/article/details/99060042
Code:
#include<map>
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 21314;
int a[maxn],sum[maxn];
int main()
{
int n;
map<int,int> ma;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=(sum[i-1]+a[i])%n;
}
for(int i=1;i<=n;i++)
{
if(sum[i]==0)
{
cout<<i<<endl;
for(int j=1;j<=i;j++)
cout<<a[j]<<" ";
break;
}
if(!ma[sum[i]]) ma[sum[i]]=1;
else if(ma[sum[i]])
{
cout<<i-ma[sum[i]]<<endl;
for(int j=1+ma[sum[i]];j<=i;j++)
cout<<a[j]<<" ";
break;
}
}
cout<<endl;
} 吃糖果
Description:
HOHO，终于从Speakless手上赢走了所有的糖果，是Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种，这样；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下。
Input
第一行有一个整数T，接下来T组数据，每组数据占2行，第一行是一个整数N（0<N<=1000000)，第二行是N个数，表示N种糖果的数目Mi(0<Mi<=1000000)。
Output
对于每组数据，输出一行，包含一个"Yes"或者"No"。
Sample Input
2
3
4 1 1
5
5 4 3 2 1
Sample Output
No
Yes
Problem solving:
这道题的意思就是说有一个小孩子喜欢吃糖但是他不喜欢一直吃一种每次都吃一样的，给你每种糖果的个数问你可不可以满足他每次吃一种的习惯。
这道题用到的也是鸽巢原理。我们考虑这种情况，有一堆糖果是最多的，多到什么地步呢，就是多到每一次吃了一个糖换口味的时候选的都是它。所以如果这个数小于等于总糖数的一半，显然你是可以满足他的习惯，反之既不可以。这样就可以了。
证明的话我也证明不来哈。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll a,n,sum,maxn,c;
cin>>n;
for(ll i=0;i<n;i++)
{
maxn=0,sum=0;
cin>>a;
for(ll i=0;i<a;i++)
{
cin>>c;
maxn=max(c,maxn);
sum+=c;
}
if((sum-maxn)>=(maxn-1)) puts("Yes");
else puts("No");
}
} Teacher Bo
Description:
Problem solving:
这道题就是给了你n个点问你存不存在每两个点之间的曼哈顿距离是相等的情况。
直接暴力就能过。
好像可以用鸽巢定理来个小优化，是暴力就能过就不优化了吧。
Code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5+10;
struct node{
int x,y;
}p[maxn];
bool flag[maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(flag,0,sizeof(flag));
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>p[i].x>>p[i].y;
}
int f=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
int mid=(abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y));
if(flag[mid])
{
puts("YES");
f=1;
}
flag[mid]=1;
if(f) break;
}
if(f) break;
}
if(!f) puts("NO");
}
} 跳蚤
Description:
Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。
Input
两个整数N和M(N <= 15 , M <= 100000000)。
Output
可以完成任务的卡片数。
Sample Input
2 4
Sample Output
12
Hint
这12张卡片分别是：
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4),
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4)
Problem solving:
这道题确实是一道好题，虽然我也没做出来。
这道题的意思是给你一个数代表跳蚤跳的最远距离，然后给你一个数n代表跳蚤可以走的不同步数的个数。问你有几种选择的方案可以让跳蚤走到左边距离为1的地方
这道题用到的有
- 快速幂
- 扩展gcd
- 容斥定理
- 二进制枚举
我们可以通过题意得知每种步数以及这个步数的个数的乘积之和为1，所以就可以用扩展gcd推出来每一项的系数的gcd为1的时候才会存在。但是找gcd为1的情况并不好找，所以我们找不为一得，总数减去为1的，就是答案。
因为总共有n个位置，我们找出来那个最大值的质因子，然后用容斥定理求出gcd不为1的总个数。这个还是看代码吧，我也说不清。
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[50];
ll poww(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1) ans*=x;
x*=x;
y/=2;
}
return ans;
}
int main()
{
ll n,m,pos=0,mm;
cin>>n>>m;
mm=m;
for(int i=2;i<=m/i;i++)//质因子分解
{
if(m%i==0)
{
a[pos++]=i;
while(m%i==0) m/=i;
}
}
if(m>1) a[pos++]=m;
ll ans=0;
for(int i=1;i<(1<<pos);i++)//二进制枚举查找gcd不为1的情况的总个数。
{
ll mid=1,miid=0;
for(int j=0;j<pos;j++)
{
if(i&(1<<j))
{
miid++;
mid*=a[j];
}
}
if(miid&1) ans+=poww(mm/mid,n);//n个位置
else ans-=poww(mm/mid,n);
}
cout<<poww(mm,n)-ans<<endl;
} 好吧，我这波强行解释不太清楚。
可以参考一下这篇博客：
https://blog.csdn.net/gyhguoge01234/article/details/77434631
投递牛客等公司7个岗位 >