题目链接 https://ac.nowcoder.com/acm/contest/977
A: 序列的第 k 个数
输入描述: BSNY 在学等差数列和等比数列, 当已知前三项时, 就可以知道是等差数列还是等比数列. 现在给你序列的前三项, 这个序列要么是等差序列, 要么是等比序列, 你能求出第 k 项的值吗. 如果第 k 项的值太大, 对 200907 取模.
第一行一个整数 T, 表示有 T 组测试数据;
对于每组测试数据, 输入前三项 a,b,c, 然后输入 k.
输出描述:
对于每组数据输出第 k 项的值, 对 200907 取模.
示例 1
输入
2 1 2 3 5 1 2 4 5
输出
5 16
说明
第一组是等差序列, 第二组是等比数列.
备注:
对于全部数据, 1≤T≤100,1≤a≤b≤c≤109,1≤k≤1091 \leq T \leq 100,1 \leq a \leq b \leq c \leq 10^9,1 \leq k \leq 10^91≤T≤100,1≤a≤b≤c≤109,1≤k≤109.
解题思路: 根据等差和等比数列的性质求解即可
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll ksm(ll a,ll b,ll p){
- ll res=1;
- while(b){
- if(b&1) res=res*a%p;
- a=a*a%p;
- b>>=1;
- }
- return res;
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- ll p=200907;
- ll a,b,c,k;
- cin>>a>>b>>c>>k;
- if(a+c==2*b) cout<<(a+(b-a)*(k-1))%p<<endl;
- else cout<<a*ksm(b/a,k-1,p)%p<<endl;
- }
- return 0;
- }
- View Code
B:A 的 B 次方
题目描述
给出三个整数 a,b,m, 求
- ab?mod?ma^b \bmod m
- a
- b
- m
- o
- d
m 的值.
输入描述:
一行三个整数 a,b,m.
输出描述:
一个整数, 表示 ab?mod?ma^b \bmod mabmodm 的值.
示例 1
输入
2 100 1007
输出
169
备注:
对于全部数据, 1≤a,b,m≤1091 \leq a,b,m \leq10^91≤a,b,m≤109.
解题思路: 扔个板子 结束
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll ksm(ll a,ll b,ll p){
- ll res=1;
- while(b){
- if(b&1) res=res*a%p;
- a=a*a%p;
- b>>=1;
- }
- return res;
- }
- int main(){
- ll a,b,m;
- cin>>a>>b>>m;
- cout<<ksm(a,b,m)<<endl;
- return 0;
- }
- View Code
C: 转圈游戏
题目描述
n 个小伙伴 (编号从 0 到 n-1) 围坐一圈玩游戏. 按照顺时针方向给 n 个位置编号, 从 0 到 n-1. 最初, 第 0 号小伙伴在第 0 号位置, 第 1 号小伙伴在第 1 号位置,......, 依此类推.
游戏规则如下: 每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置, 第 1 号位置小伙伴走到第 m+1 号位置,......, 依此类推, 第 n−m 号位置上的小伙伴走到第 0 号位置, 第 n-m+1 号位置上的小伙伴走到第 1 号位置,......, 第 n-1 号位置上的小伙伴顺时针走到第 m-1 号位置.
现在, 一共进行了
10k10^k
1
0
k 轮, 请问 x 号小伙伴最后走到了第几号位置.
输入描述:
输入共 1 行, 包含 4 个整数 n,m,k,x, 每两个整数之间用一个空格隔开.
输出描述:
输出共 1 行, 包含 1 个整数, 表示 10k10^k10k 轮后 x 号小伙伴所在的位置编号.
示例 1
输入
10 3 4 5
输出
5
备注:
对于 30% 的数据, 0 <k <7;
对于 80% 的数据, 0<k<1070 < k <10^70<k<107;
对于 100% 的数据, 1<n<1061< n < 10^61<n<106,0<m>,0<k<1090<k < 10^90<k<109.</m>
解题思路: 规律:(x+m*ksm(10,k,n)%n)%n
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll ksm(ll a,ll b,ll p){
- ll res=1;
- while(b){
- if(b&1) res=res*a%p;
- a=a*a%p;
- b>>=1;
- }
- return res;
- }
- int main(){
- ll n,m,k,x;
- cin>>n>>m>>k>>x;
- cout<<(x+m*ksm(10,k,n)%n)%n<<endl;
- return 0;
- }
- View Code
D: 越狱
题目描述
监狱有连续编号为 1 到 n 的 n 个房间, 每个房间关押一个犯人. 有 m 种宗教, 每个犯人可能信仰其中一种. 如果相邻房间的犯人信仰的宗教相同, 就可能发生越狱. 求有多少种状态可能发生越狱.
输入描述:
输入两个整数 m 和 n.
输出描述:
可能越狱的状态数, 对 100003 取余.
示例 1
输入
2 3
输出
6
说明
所有可能的 6 种状态为:{0,0,0 }, {0,0,1 }, {0,1,1 }, {1,0,0 }, {1,1,0 }, {1,1,1 }.
备注:
对于全部数据, 1≤m≤108,1≤n≤10121 \leq m \leq 10^8,1 \leq n \leq 10^{12}1≤m≤108,1≤n≤1012.
解题思路: 正难则反; 总的可能 - 发生越狱的可能数
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll ksm(ll a,ll b,ll p){
- ll res=1;
- while(b){
- if(b&1) res=res*a%p;
- a=a*a%p;
- b>>=1;
- }
- return res;
- }
- int main(){
- ll m,n;
- ll p=100003;
- cin>>m>>n;
- cout<<((ksm(m,n,p)-m*ksm(m-1,n-1,p))%p+p)%p<<endl;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3399200.html