int main(){
int k,i,tail[LEN],m,flag;
while(scanf("%d",&k)!=EOF)
{
if(k==0) break;
flag=0;
i=m=1;
memset(tail,0,sizeof(tail));
if(k>=LEN)
{
k=k%LEN;
flag=1;
}
while(1){
i*=k;
if(i>=LEN || flag==1)
{
if(tail[i%LEN]==0) tail[i%LEN]=m;
else {tail[i%LEN]+=m;break;}
flag=1;
}
if(i>=LEN) i=i%LEN;
m++;
}
printf("%d\n",tail[i%LEN]);
}
}
B 3n+1 数链问题
直接模拟 RMQ一直没有实现
代码
#include <iostream>
#include <stdlib.h>
using namespace std;
int done(int i, int j)
{
int max=0,count,n;
for(int m=i; m<=j; m++){
count=1;
n=m;
while(n!=1){
if(n%2==0)
n=n/2;
else
n=n*3+1;;
count++;
}
if(count>max) max=count;
}
return max;
}
int main()
{
int i,j,sum;
while(cin>>i>>j){
if(i==0&&j==0) break;
if(i>j) sum=done(j,i);
else sum=done(i,j);
cout<<sum<<endl;
}
return 0;
}
C计算a^b mod c
代码
int modular(int a,int b,int m)
{
int t=a,tt=1;
while(b)
{
if(b%2)tt=(tt*t)%m;
t=(t*t)%m;
b/=2;
}
return tt;
}
D 负权数
算法思想：
当n>0且r>0时
n=an*r^n+an-1*r^(n-1)+…+a0*r^0;
现在讨论r<0的情况
如果n>0
n=an*|r|^n+an-1*|r|^(n-1)+…+a0*|r|^0;
设其中某项为ap*|r|^p且p!=0
当p为偶数的时候ap*r^p不变
当p为奇数的时候则变为相反数
构造
ap*|r|^p=r^(p+1)+(|r|- ap)*r^p;
如果n<0
当p为奇数的时候不变
当p为偶数的变为相反数
算法步骤：
对n和r取绝对值
将|n|表示为|r|进制然后根据n的正负针对构造进行相应的操作
既将本位换为|r|-ap并且对高位加一
代码相关问题：
子函数tentor：将十进制n转换为r进制
子函数increase: 实现高位进位的操作可能改变数字的位数
子函数output：高于十进制的表示方法
注意对0的处理
代码
#include <stdio.h>
#include <string.h>
#include <math.h>
int n,r,nn,rr,num[101],p,len;
void tentor()
{
int a,b;
a=nn,b=rr,len=0;
memset(num,0,sizeof(num));
while(a)
{
num[len++]=a%b;
a/=b;
}
}
void increase(int p)
{
while(++num[p]>=rr)
{
num[p]=rr-num[p];
p++;
}
if(p>=len) len++;
}
void output()
{
int i;
for(i=len-1;i>=0;i--)
{
if(num[i]<10) printf("%d",num[i]);
else printf("%c",55+num[i]);
}
printf("\n");
}
int main()
{
while(scanf("%d%d",&n,&r)!=EOF)
{
if(n==0&&r==0) break;
if(n==0) printf("0\n");
else
{
nn=fabs(n);
rr=fabs(r);
tentor();
p=n>0?1:0;
for(;p<len;p+=2)
{
if(num[p]!=0)
{
num[p]=rr-num[p];
increase(p+1);
}
}
output();
}
}
}
G:数值转换
我是直接观察的出的结论
代码
#include<stdio.h>
#include<string.h>
char num[1002];
int len;
int main()
{
int n,t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
len=0;
if(n==0)
printf("0\n");
else
{
while(n!=0){
if(n>0)
switch(n%3){
case 0: num[len++]='0'; n/=3; break;
case 1: num[len++]='1'; n=(n-1)/3; break;
case 2: num[len++]='-'; n=(n+1)/3; break;
}
else
switch(-n%3){
case 0: num[len++]='0'; n/=3; break;
case 1: num[len++]='-'; n=(n+1)/3; break;
case 2: num[len++]='1'; n=(n-1)/3; break;
}
}
while(--len>=0) putchar(num[len]);
puts("\0");
}
}
}
还有质多项式 猴子舞 大众匹萨没有作出来 做出来再贴