数制转换有两种题型，一般一题，分值1.5分。
题型一：R进制转十进制
解法就是：按权展开，但要注意各个位的权，最低位（最右边）的权是0次方，权值为1。
纯整数的情况：
(11010110)2 = 1×27 + 1×26 + 0×25 + 1×24 + 0×23 + 1×22 + 1×21 + 0×20 = (214)10
(2365)8 = 2×83 + 3×82 + 6×81 + 5×80 = (1269)10
(4BF)16 = 4×162 + B×161 + F×160 = (1215)10
整数带小数的情况：
(110.011)2 = 1×22 + 1×21 + 0×20 + 0×2-1 + 1×2-2 + 1×2-3 = (6.375)10
(5.76)8 = 5×80 + 7×8-1 + 6×8-2 = (5.96875)10
(D.1C)16 = D×160 + 1×16-1 + C×16-2 = (13.109375)10
题型二：十进制转R进制
注意：十进制的小数转R进制未必可以转完。
每日练习
一、任意进制转十进制
1、(1101101)2 = ( )
2、(7754)8 = ( )
3、(F1B9AC)16 = ( )
4、(1011.11101)2 = ( )
5、(75.1076)8 = ( )
6、(59D.10AC)16 = ( )
二、十进制转任意进制
1、(173)10 = ( )2
2、(173.125)10 = ( )2
3、(173)10 = ( )8
4、(173.625)10 = ( )8
5、(173)10 = ( )16
6、(173.375)10 = ( )16
往年真题
1. 与16进制数 A1.2等值的10进制数是( )
A．101.2 B．111.4 C．161.125 D．177.25
2. 2E+03表示( )
A．2.03 B．5 C．8 D．2000
3. 在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是( )
A．19 B．-19 C．18 D．-18
4. 十进制小数125.125对应的八进制数是( )
A．100.1 B．175.175 C．175.1 D．100.175
5. 与十进制数28.5625相等的四进制数是( )
A．123.21 B．131.22 C．130.22 D．130.21 E．130.20
6. (2008)10+ (5B)16 的结果是( )。
A．(833)16 B．(2099)10 C．(4063)8 D．(100001100011)2
7. 与十进制数28.5625相等的四进制数是( )。
A. 123.21 B. 131.22 C. 130.22 D. 130.21
8. (2008)10+ (5B)16的结果是( )。
A. (833)16 B. (2089)10 C. (4163)8 D. (100001100011)2
9. 算式 (1000)10－(100)16－(10)8的结果是( )。
A. (890)10 B. (986)8 C. (1011100000)2 D. (2E0)16 E. (736)10
10. 与十进制数17.5625相对应的8进制数是( )
A. 21.5625 B. 21.44 C. 21.73 D. 21.731 E. 前4个答案都不对
11. (2070)16+(34)8的结果是( ).
A. (8332)10 B. (208C)16 C. (100000000110)2 D. (20214)8
题解：统一为二进制运算，然后再转其他进制
12. 与十进制数1770对应的八进制数是( )。
A．3350 B．3351 C．3352 D．3540
13. (2070)16 + (34)8 的结果是( )。
A．(8332)10 B．(208A)16 C．(100000000110)2 D．(20212)8
14. 与十进制数1770.625对应的八进制数是( )。
A. 3352.5 B. 3350.5 C. 3352.1161
D. 3350.1151 E. 前4个答案都不对
15. (2010)16 + (32)8的结果是( )。
A. (8234)10 B. (202A)16 C. (100000000110)2 D. (2042)16
真题参考答案：
1A 2BC 3B 4A 5A 6B 7AC
8AD 9D 10C 11E 12AC 13A 14A
文件读入读出
假设题目名为“add”，那么文件夹名为“add”，c++程序名为“add.cpp”，读入文件名为“add.in”，输出文件名为“add.out”。四个的拼写均不可有误，包括大小写差异。千万不要调试后就忘记修改文件读入读出了。
#include<cstdio>
int main(){
freopen("add.in","r",stdin);//read
freopen("add.out","w",stdout);//write
}
数论算法
1、线性筛
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
const int maxn=200005;
int prime[maxn];
bool not_prime[maxn];
int main()
{
int n,cnt=0;
scanf("%d",&n);
memset(not_prime,0,sizeof(not_prime));
not_prime[1]=true;
for(inti=2;i<=n;i++)
{
if(!not_prime[i])
prime[++cnt]=i;
for(intj=1;j<=cnt;j++)
{
if(prime[j]*i>n) break;
not_prime[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
for(inti=1;i<=cnt;i++)
printf("%d ",prime[i]);
return 0;
}
2、埃氏筛
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
inline int read()
{
char c;
c=getchar();
for(;c>'9'||c<'0';c=getchar());
int sum=0;
for(;c<='9'&&c>='0';c=getchar())sum=sum*10+c-48;
return sum;
}
int n,m;
bool f[10010000];
int main()
{
n=read(),m=read();
memset(f,true,sizeof(f));
f[0]=f[1]=false;
for(inti=2;i<=n;i++)
if(f[i])
for(intj=2;i*j<=n;f[i*j]=false,j++);
for(inti=1;i<=m;i++)
{
int x;
x=read();
if(f[x])printf("Yes\n");
elseprintf("No\n");
}
return 0;
}
3、拓展欧几里得算法
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int x,y;
int exgcd(int a,int b)
{
if(!b)
{
x=1;
y=0;
return a;
}
else
{
int t;
intd=exgcd(b,a%b);
t=x;
x=y;
y=t-a/b*x;
return d;
}
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
exgcd(a,b);
// cout<<__gcd(a,b)<<endl;
cout<<x<<" "<<y<<endl;
return 0;
}
4、GCD&LCM（求最小公倍数与最大公约数） 暂时代码是转载的
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int gcd(int a,int b)
{
if(!b) returna;
else returngcd(b,a%b);
}
int lcm(int a,int b)
{
returna/gcd(a,b)*b;
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
cout<<gcd(a,b)<<" "<<lcm(a,b)<<endl;
return 0;
}
5、分解质因数
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int main()
{
long long n;
scanf("%lld",&n);
for(long longi=2;i<=n;i++)
{
while(n!=i)
{
if(n%i==0)
{
printf("%lld*",i);
n=n/i;
}
elsebreak;
}
}
printf("%lld",n);
return 0;
}
6、大数翻倍法
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[233],mo[233];
int gcd(int a,int b)
{
if(!b) returna;
else returngcd(b,a%b);
}
int lcm(int a,int b)
{
returna/gcd(a,b)*b;
}
int main()
{
int n;
scanf("%d",&n);
for(inti=1;i<=n;i++)
scanf("%d%d",&a[i],&mo[i]);
intans=0,nowmo=1;
for(inti=1;i<=n;i++)
{
intother=a[i],othermo=mo[i];
if(othermo>nowmo)
{
swap(ans,other);
swap(nowmo,othermo);
}
while(ans%othermo!=other)
ans+=nowmo;
nowmo=lcm(nowmo,othermo);
}
printf("%d",ans);
}
7、快速幂
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1007;
int xx(int a,int n,int MOD)
{
int ret=1;
int tmp=a%MOD;
while(n)
{
if(n&1)
ret=ret*tmp%MOD;
tmp=tmp*tmp%MOD;
n>>=1;
}
return ret;
}
int main()
{
int m,n;
while(scanf("%d%d",&m,&n)==2)
{
printf("%d\n",xx(m,n,MOD));
}
}
8、位运算
|
功能 |
示例 |
位运算 |
|
去掉最后一位 |
(101101->10110) |
x >> 1 |
|
在最后加一个0 |
(101101->1011010) |
x << 1 |
|
在最后加一个1 |
(101101->1011011) |
x << 1+1 |
|
把最后一位变成1 |
(101100->101101) |
x | 1 |
|
把最后一位变成0 |
(101101->101100) |
x | 1-1 |
|
最后一位取反 |
(101101->101100) |
x ^ 1 |
|
把右数第k位变成1 |
(101001->101101,k=3) |
x | (1 << (k-1)) |
|
把右数第k位变成0 |
(101101->101001,k=3) |
x & !(1 << (k-1)) |
|
右数第k位取反 |
(101001->101101,k=3) |
x ^ (1 << (k-1)) |
|
取末三位 |
(1101101->101) |
x & 7 |
|
取末k位 |
(1101101->1101,k=5) |
x & (1<< k -1) |
|
取右数第k位 |
(1101101->1,k=4) |
x >> (k-1) & 1 |
|
把末k位变成1 |
(101001->101111,k=4) |
x | (1 << k-1) |
|
末k位取反 |
(101001->100110,k=4) |
x ^ (1 << k-1) |
|
把右边连续的1变成0 |
(100101111->100100000) |
x & (x+1) |
|
把右起第一个0变成1 |
(100101111->100111111) |
x | (x+1) |
|
把右边连续的0变成1 |
(11011000->11011111) |
x | (x-1) |
|
取右边连续的1 |
(100101111->1111) |
(x ^ (x+1)) >> 1 |
|
去掉右起第一个1的左边 |
(100101000->1000) |
x & (x ^ (x-1)) |