【数论专题】BT-BY(基础上机试题)

BT: 美丽数

小明很喜欢3和5这两个数字,他将能被3或5整除的数叫做美丽数。现在给你一个整数N(1<=N<=100000),你能告诉小明第N个美丽数是多少吗?
提示 本题需要打表优化
参考代码:
https://paste.ubuntu.com/p/th...
输入
输入包含多组测试数据。每组输入一个整数N(1<=N<=100000)。
输出
对于每组输入,输出第N个美丽数。
样例输入 Copy
1
2
3
4
样例输出 Copy
3
5
6
9

//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//using namespace std;
//
//int main(){
//    int n = 0;
//    int a[100005];
//    int count = 1;
//    for(int i = 1;; i++){//需要使用数组先把对应的漂亮数存下来然后后面直接访问数组下标即可,要不查找时时间会超限 
//        if(i % 3 == 0 || i % 5 == 0){
//            a[count] = i;
//            count ++;
//        }
//        if(count > 100000){
//            break;
//        }
//    }
//    while(scanf("%d",&n) != EOF){
//        printf("%d\n",a[n]);
//    }
//    return 0;
//} 

BU: 一个数学问题

给你两个整数n和m,请你计算有多少个整数对(a,b)满足以下条件:
当0<a<b<n时,(a^2+b^2+m)/(ab)是一个整数。
输入
输入包含多组测试数据。每组输入为两个整数n和m(0<n<=100),当n=m=0时,输入结束。
输出
对于每组输入,输出样例标号和满足要求的整数对的个数。
样例输入 Copy
10 1
20 3
30 4
0 0
样例输出 Copy
Case 1: 2
Case 2: 4
Case 3: 5

//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//using namespace std;
//
//int main(){
//    int n = 0, m = 0,count = 1;
//    while(scanf("%d %d",&n,&m),m || n){
//        int s = 0;
//        for(int a = 1; a < n; a++){
//            for(int b = a + 1; b < n; b++){
//                if((a * a + b * b + m) % (a * b) == 0){
//                    s++;
//                }
//            }
//        }
//        printf("Case %d: %d\n",count,s);
//        count ++;
//    }
//    return 0;
//} 

BV: 找新朋友

新年快到了,天勤准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。
输入
第一行是测试数据的组数CN(Case number,1<CN<10000),接着有CN行正整数N(1<n<32768),表示会员人数。
输出
对于每一个N,输出一行新朋友的人数,这样共有CN行输出。
样例输入 Copy
2
25608
24027
样例输出 Copy
7680
16016

//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//using namespace std;
//
//int main(){//这种方法虽然能得出正确答案,但是时间复杂度较大,后面用欧拉方程计算 
//    int cn = 0;
//    int a[32769];
//    scanf("%d",&cn);
//    while(cn--){
//        int n = 0,count = 0;
//        int i,j;
//        scanf("%d",&n);
//        for(i = 1; i < n; i++){
//            for(j = 2; j < n; j++){
//                if(i % j == 0 && n % j == 0){
//                    break;
//                }
//            }
//            if(j == n){
//                count ++;
//            }
//        }
//        printf("%d\n",count);
//    }
//    return 0;
//} 

下面用欧拉函数相关定理的方法来解决这道题

///*
//欧拉φ函数:φ(n)是所有小于n的正整数里,和n互素的整数的个数。n是一个正整数。   
//欧拉证明了下面这个式子:   
//如果n的标准素因子分解式是p1^a1*p2^a2*……*pm^am,其中众pj(j=1,2,……,m)都是素数,而且两两不等。
//则有   φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)   
//利用容斥原理可以证明它。
//*/
//
//#include <iostream>
//#include <cmath>
//using namespace std;
//int euler(int x)
//{
//    // 就是欧拉公式
//    int i, res=x;
//    for (i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
//        if(x%i==0)
//        {
//            res = res / i * (i - 1);
//            while (x % i == 0) x /= i; // 保证i一定是素数
//        }
//    if (x > 1) res = res / x * (x - 1);
//    return res;
//}
//int main(void)
//{
//    int n;
//    cin>>n;
//    while(n--)
//    {
//        int a;
//        cin>>a;
//        cout<<euler(a)<<endl;
//
//    }
//}

BW: sqrt log sin 函数

小明的老师给小明布置了这样一道作业题,一个序列符合以下定义:

image.png
现问你这个序列的第n项是多少?

输入
输入包含多组测试数据。每组输入一个整数n(0<=n<=1000000),当输入-1时,输入结束。
输出
对于每组输入,输出第n项的值,结果请mod 1000000。
样例输入 Copy
0
-1
样例输出 Copy
1

//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<cmath> 
//using namespace std;
///*
//在运行代码的时候,操作系统会分配不同的内存区域来运行代码
//
//栈区:由操作系统自动分配释放,存放函数的参数值,局部变量的值;不需要时系统会自动清除
//堆区:由new分配的内存块,也就是说在代码中new一个数组,内存由堆区分配;堆区不由编译器管,由应用程序控制(相当于程序员控制。如果程序员没有释放掉,程序结束后,操作系统会自动回收
//数据区:也称全局区或者静态区,存放全局的东西,比如全局变量(大数组尽量定义在main函数外,即放在数据区)
//代码区:存放执行代码的地方,类似if else,while,for这种语句
//*/ 
//
//int a[1000005];//超大数组不应定义在main函数内,因为main函数内部数组会被分配在栈内(栈比较小),容易导致栈溢出 
//int main(){
//    int n = 0;
//    double x,y,z,i;
//    a[0] = 1;
//    for(i = 1; i <= 1000000; i++){
//        x = i - sqrt(i);//注意i需要定义为double类型,因为其参与的运算结果需赋值给double类型x.y.z 
//        y = log(i);//log()log是e为底的对数(对应ln),log10()是10为底的对数 
//        z = i * sin(i) * sin(i);
//        a[(int)i] = (a[(int)x] + a[(int)y] + a[(int)z]) % 1000000;
//    }
//    while(scanf("%d",&n) != EOF,n != -1){
//        printf("%d\n",a[n]);
//    }
//    return 0;
//} 

BX: 算步数

给你坐标轴上的两个点A和B,请问从A走到B最少需要多少步?
我们对走的每一步的步长作出如下限制:
第一步和最后一步的步长必须是1,其他的任意一步的步长必须比前一步的步长小1、大1或相等。
输入
输入包含多组测试数据。每组输入两个整数A和B(0<=A<=B<2^31)。
输出
对于每组输入,输出从A走到B最少需要多少步。
样例输入 Copy
45 48
45 49
45 50
样例输出 Copy
3
3
4

//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//using namespace std;
////要知道公式1+2+。。+n+。。+2+1=n*n,找到平方小于等于差值的的数字t
//int main(){
//    long a = 0,b = 0,c,n,t,bu = 2;//bu代表要走的总步数 = 2,首尾必须各走一步 
//    while(scanf("%ld %ld",&a,&b) != EOF){
//        c = b - a;
//        if(c == 0){
//            printf("0\n");
//            continue;
//        }
//        for(t = 0; t * t <= c; t++);//此处只循环找到最小的t,只有循环条件,没有循环体 
//        t = t - 1;//找到平方小于等于差值的的数字t,最后求余,不得零就总数加1,还有int会超时,要改用long int
//        bu = 2 * t - 1; //计算目前步数 
//        n = (c - t * t) / t;//先求商,看还能有几个最大步数 
//        bu += n;//把计算得到剩余的最大步数放在最大步数之后(如1234567654321中7之后 ),总步数增加/n步 
//        if((c - t * t) % t == 0){
//            printf("%ld\n",bu);
//        }else{
//            printf("%ld\n",bu + 1);//最后求余,不得零代表还剩余步数,则多加一小步走完,总步数bu加1
//        }
//    }
//    return 0;
//} 

BY: 寻找最低数

给你一个正整数A(1<=A<=100),输出A的最低数。
例如,给你A=26,我们可以将A化成二进制为11010,则A的最低数是10,输出10的十进制为2。
再例如,给你A=88,我们可以将A化成二进制为1011000,则A的最低数是1000,输出为8。
输入
输入包含多组测试样例。每行输入一个正整数A(1<=A<=100)。当输入0时,输入结束。
输出
对于每一个输入,输出对应的最低数。
样例输入 Copy
26
88
0
样例输出 Copy
2
8

//#include<iostream>
//#include<algorithm>
//#include<string>
//#include<string.h>
//#include<cmath>
//#include<math.h>
//using namespace std;
//
//int main(){ 
//    int t = 0,i,j,k,a[15];
//    while(scanf("%d",&t) != EOF){
//        if( t == 0){
//            break;
//        } 
//        i = 0;
//        while(t){//十进制转二进制,切记计算得到的01.....逆序排列才是得到的二进制 
//            a[i++] = t % 2;
//            t /= 2;
//        }
////        while(t != 0){//二进制转十进制 
////            a = t % 10;
////            t /= 10;
////            b = a * pow(2,k++);
////        }
//        k = 0;
//        for(j = 0; j < i; j++){
//            if(a[j] == 1){
//                break;
//            }else{
//                k++;//统计1前面有多少个0 
//            }
//        }
////        int test  = pow(2,k);//此处需注意printf()在传递参数的时候不会进行类型转换
////        cout << test;
//        printf("%d\n",(int)pow(2,k));//而pow()的返回值是一个double型的值,故需在前面加(int)
////        printf("%d\n",test); 
//    }
//    return 0;
//} 

评论

暂无评论