流离之人追逐幻影

用户名：pwj666

访问量：60209

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13957
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：186

你可能喜欢

A+B for Input-Output Practice (VII) （C语言代码）

暑二集训--总结

　　作者: 流离之人追逐幻影　　　　发表时间：2019-08-28 16:14:33 浏览：227　|　评论：0　

1.求余数Ⅰ
```
描述
（这周的集训题目类型相似的，本题题难度最低，是开始本周集训的一道开胃小菜）
输入一个正整数n，要求输出n除以3之后得到的余数。
```
```
输入
有个多用例，在一行输入一个正整数n，代表需要求余的整数。

输出
输出n除以3之后的余数（行尾需要换行）。
```
```
输入样例 1

123
2147483647
输出样例 1

0
1
```

题解：给萌新做的。
```
#include<bits/stdc++.h>
using namespace std;

int main(){
    long long n;
    while(cin>>n){
        cout<<n%3<<endl;

}
    return 0;
}
```

2.求余数Ⅱ
```
描述

同样还是求一个整数除以3之后的余数，但是这个整数跟前面的有点不一样，在该题中输入的整数是一个大数（大数是指计算的数值非常大或者对精度要求非常高，用已知的数据类型无法表示的数值，比如1<=N<=1,000,000,000,000,000,000的范围，N就可能是一个大数），要求输出该数除以3之后得到的余数。
```
```
输入
输入有多个用例，在一行输入一个正整数n(1 <=n<= 10^19)，代表需要求余的整数。

输出
输出n除以3之后的余数。
```
```
输入样例 1

1234
11111111111111111
输出样例 1

1
2
```
题解： 爆数，给萌新的小坑
```
#include<bits/stdc++.h>
using namespace std;

int main(){
    string n;
    long long sum;
    while(cin>>n){
            sum=0;
        for(int i=0;i<n.length();i++)
            sum+=n[i];
        cout<<sum%3<<endl;

}
    return 0;
}
```

3.求余数Ⅲ
```
描述

要解决的仍然是一个求余问题，但是这次不再是求除以3的余数。要求输入一个整数(该整数同样是一个大数)，输出该数除以12之后的余数。
```
```
输入
输入有个多用例，在一行输入一个整数n(1 <=n<= 10^18)，代表需要求余的整数。

输出
输出n除以12之后的余数。
```
```
输入样例 1

1234
111111111111111111111111111111
输出样例 1

10
3
```
题解：
解法一：同余定理 (a+b)%c=(a%c+b%c)%c
[https://blog.csdn.net/foradawn/article/details/53170520](https://blog.csdn.net/foradawn/article/details/53170520)
```
#include<cstdio>
#include<cstring>

int main()
{
	char a[1010];
	int b = 12;
	while(~scanf("%s",a)){
	
	int l,y;
	l=strlen(a);
	y=(a[0]-'0')%b;
	
	for(int i=1;i<l;i++){
	y=(y*10+a[i]-'0')%b;
	
	}
	printf("%d\n",y);
	}
}
```
解法二：制作12和3,4的余数对照表，根据除以3，4的余数从表中找出符合条件的余数，然后找出除以12的余数。
![](/image_editor_upload/20190828034519_13472.png)
```
#include<iostream>
#include<string>
using namespace std;

int judge(int t,int f){
	int twelve[12]={0,1,2,3,4,5,6,7,8,9,10,11},
	three[12]={0,1,2,0,1,2,0,1,2,0,1,2},
	four[12]={0,1,2,3,0,1,2,3,0,1,2,3};

for(int i=0;i<12;i++){
		if(t==three[i]){

if(f==four[i])

return twelve[i];        //在对照表中找到相应的位置，返回所得结果
		}
	}

}

int answer(string n){

int i,tsum=0,fsum,t,f;

for(i=0;i<n.length();i++){
	tsum=tsum+n[i]-'0';      //求得整数n每一位数字相加的总和tsum
	}
	t=tsum%3;  //求得整数n除以3的余数t

if(n.length()>1)
	fsum=n[n.length()-1]-'0'+(n[n.length()-2]-'0')*10;
	//如果n是两位以上的数，获取n的最后两位数fsum

else
	fsum=n[n.length()-1]-'0';//如果n一位数，fsum直接等于n
	f=fsum%4;//求得整数n除以4的余数f

return judge(t,f);
	}
	int main(){
	string n;
	while(cin>>n)  //输入整数n
	{
	cout<<answer(n)<<endl;
	}
}
```
4.求余数Ⅳ
```
描述

阶乘是基斯顿·卡曼（Christian Kramp，1760～1826）于1808年发明的运算符号，是数学术语。一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。亦即n!=1×2×3×...×n。

阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。给出两个整数m,n(m<n)，n和m都可以很大，但最大不超过20位，需要你求出该整数n的阶乘除以(n-m)的余数是多少。

(当n = 20时，n!已经超出了int的表示范围。)
```
```
输入
输入包括多个用例，每组用例一行，包括两个正整数m,n(先输入m，再输入n，中间用一个空格隔开)。

输出
对于每个测试用例，输出n!除以(n-m)之后的余数。
```
```
输入样例 1

12345 123456789
输出样例 1

0
```
题解：n-m 肯定是n!其中的一个因数，这题目出的水
```
#include<bits/stdc++.h>
using namespace std;
int main(){
    string m,n;
    while(cin>>m>>n){
            cout<<0<<endl;

}
    return 0;
}
```
5.求余数Ⅴ
```
描述

阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。给出一个整数n(1<=n<=1000)，需要你求出该整数n的阶乘除以(n+2)的余数是多少。

(当n = 20时，n!已经超出了int的表示范围。)
```
```
输入
输入包括多个用例，每组用例一行，只有一个整数n(n<=1000)。

输出
对于每个测试数n，输出n!除以(n+2)之后的余数。
```
```
输入样例 1

1
2
3
输出样例 1

1
2
1
```
题解：首先列出n=10之前的的余数，发现如果n为质数时（除1，2外）余数为1，为合数时余数为0，然后就可以另辟蹊径AC.
（我的）解法一：
```
#include<bits/stdc++.h>
using namespace std;
int ss(int n){
    for(int i=2;i<=(n+2)/2;i++)
            if((n+2)%i==0)
                return 0;
    return 1;
}

int main(){
    int m,n;
    while(cin>>n){
            if(n==1) {
                cout<<1<<endl;
                continue;
            }
            if(n==2){
                cout<<2<<endl;
                continue;
            }
            cout<<ss(n)<<endl;
    }
    return 0;
}
```
（学校的）解法二：正面刚，高精度算出阶乘，直接求余数
```
#include<iostream>
#include<string>
using namespace std;

int a[100005];

int w = 1;//位数初始为1

string fac(int n){//求阶乘

string str;

for (int z = 1; z <= n; z++){

int x = 0;

for(int i = 1; i <= w; ++i){

a[i] = a[i]*z + x;//算出相乘后的结果

x = a[i]/10;//如果x=0说明a[i]<10,即无进位；若x>0则有进位

a[i] = a[i]%10;//将i位的数字算出来，其实是取整

}

while (x > 0)//有进位{

w++;//位数+1

a[w] = x%10;//进位的数字

x = x/10;

}

for(int j=w;j>=1;--j) str+= a[j]+'0';//将数组中的内容放到string里面

return str;

}

int mod(string str,int n)//求余数
{
    int l,y;

l=str.length();

y=(str[0]-'0')%n;//同余定理

for(int i=1;i<l;i++){

y=(y*10+str[i]-'0')%n;

}

return y;

}

int main()
{
    int n;
    while(cin>>n){
        a[1] = 1;
        w = 1;
        cout<<mod(fac(n),(n+2))<<endl;

}

}
```
求余数Ⅵ
```
描述

这次的求余数难度进一步加大，同样也是涉及到大数求余的问题，而且涉及到的内容也更加广泛。（当然这也难不倒聪明的你们）。首先给出一个数字n，你需要做的就是求出n^n(n的n次方)的最高位数字k(即最左边的一位)，求出k之后再求n^n除以k的余数。

例如：当n=1，n^n=1，k=1，n^n%k=0;当n=3,n^n=27,k=2,n^n%k=1;

可知，当n很大的时候，n^n已经是一个不可估量的值了，为了降低题目难度，将n的取值规定为1到143之间(1<=n<=143)
```
```
输入
输入包含t+1行，其中t代表测试实例数。

接下来的t行分别是一个代表n的数(1<=n<=143)

输出
对于每个测试数n，输出n^n的最高位数字k以及n^n除以k之后所得的余数。

注意输出结果要包含具体的测试实例序号，具体格式如样例所示：
```
```
输入样例 1

3
1
2
3
输出样例 1

Case 1: 1 0
Case 2: 4 0
Case 3: 2 1
```
题解：难度主要在输出n^n的最高位数字k
[求N^N的最高位](https://blog.csdn.net/weixin_43731785/article/details/88054714 "求N^N的最高位")
```
步骤1：先求出该n^n的最高位数。

在此处涉及到两个库函数

C 库函数 double pow(double x, double y) 返回 x 的 y 次幂，即 x^y

C 库函数 double log10(double x) 返回 x 的常用对数（基数为 10 的对数）

利用pow()函数可求得n^n，再利用log10求得其位数。

假设n^n的位数为m

求一个数的最高位，可以用该数除以m*10。

例如，n=1000,n的最高位=1000/(4-1)*10=1;

所以用pow(n,n)/pow(10,m-1);可求得最高位k。

步骤二：求n^n除以最高位数k得到的余数。

要求a^n，如果知道了 a^(n/2) 次方的话，再来个平方就可以了。那么按照这个思路就能运用分治的思想了。

编写_pow函数，
```
```
#include<bits/stdc++.h>
using namespace std;
const double PI=acos(-1.0);
const double e=exp(1.0);

int g(int n){
    int s;
    double a=n*log10(n);
    s=(int)pow(10.0, a-(long long)a);
    return s;
}
int f1(int n){
    long long sum=n;
    for(int i=1;i<=10;i++){
        sum*=n;
    }
    return sum%g(n);
}
int main()
{

int n,t;
    int ct=0;
    while(cin>>t)
    {
        ct=0;
        for(int i=0;i<t;i++){
            cin>>n;
            cout<<"Case "<<++ct<<": "<<g(n)<<" "<<f1(n)<<endl;
        }

}
    return 0;
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

简单的a+b （C语言代码）

小明A+B （C语言代码）

兰顿蚂蚁（C++代码）

暑二集训--总结

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-输出正反三角形（C++代码）

WU-链表数据求和操作（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

用筛法求之N内的素数。（C语言代码）

整除问题（C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

众数问题（C语言代码）

班级人数（C语言代码）

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

A+B for Input-Output Practice (VII) （C语言代码）

简单的a+b （C语言代码）

小明A+B （C语言代码）

兰顿蚂蚁 （C++代码）

暑二集训--总结

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-输出正反三角形 （C++代码）

WU-链表数据求和操作 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C++代码）

用筛法求之N内的素数。 （C语言代码）

整除问题 （C语言代码）

第三届阿里中间件性能挑战赛-总决赛亚军比赛攻略

众数问题 （C语言代码）

班级人数 （C语言代码）

兰顿蚂蚁（C++代码）

　　评论区

WU-输出正反三角形（C++代码）

WU-链表数据求和操作（C++代码）

用筛法求之N内的素数。（C语言代码）

整除问题（C语言代码）

众数问题（C语言代码）

班级人数（C语言代码）