剰余による分類 - c21coterie @ ウィキ

大学への数学　マスターオブ整数論をプログラムで解くページ。

問い8-１　
１０個の自然数が小さい順に並んでいる。
大きい数字-小さい数字が６の倍数になる数はいくつか？
計算量ｎの解法と、計算量n＾２/2の解法。
数字列が前の数の２倍以上になってることを利用しています。
この条件を満たしてない場合std::set等を使う必要があります。

#include<stdio.h>
int main(){
int nums[]={1,3,6,14,29,60,121,249,501,1003};
int count[6]={0};
int ans=0;
for(int i=0;i<10;i++){
	int m=nums[i]%6;
	ans+=count[m];
	count[m]++;
}
printf("解法１による解=%d\n",ans);
ans=0;
for(int i=1;i<10;i++){
	for(int j=0;j<i;j++){
		ans+=((nums[i]+nums[j])%6==0);
	}
}
printf("解法２による解=%d\n",ans);
}

問い8-2

mod(13ｎ+5,11)==0となる自然数nを小さい方から３つあげよ。

#include<stdio.h>
void calc(int a,int b,int c,int no){
int m=(a+b)%c;
int size=1;
int ans=(m==0);
for(int i=2*a+b;i%c!=m;i+=a){
	if(i%c==0)ans=size;
	size++;
}
for(int i=0;i<no;i++){
	printf("%d\n",(ans+1+i*size));
}
}
int main(){
calc(13,5,11,3);
}

問い8-3

証明問題なので割愛。Lisp使えば証明できるらしいです。

問い8-4

２乗しても下ふたケタの数が変わらない２桁の自然数を全て求めよ。
2次方程式で解くのが本筋ですがまあ桁も小さいのでこれでもいいかと。

#include<stdio.h>
int main(){
for(int i=10;i<100;i++){
	if(i==(i*i)%100)printf("%d ",i);
}
printf("\n");
for(int i=10;i<100;i++){
	if((i==(i*i)%100)&&(i*i)>=1000){
		printf("%d ",i*i);
	}
}
}

問い8-5

1^100～100＾100までをそれぞれ１２で割ったあまりのうち異なるものは何通りか？

#include<stdio.h>
int main(){
bool hit[12];
for(int i=0;i<12;i++)hit[i]=false;
for(int i=1;i<=12;i++){
	int t=i;
	for(int j=1;j<100;j++){
		t=(t*i)%12;
	}
	hit[t]=true;
}
int ans=0;
for(int i=0;i<12;i++)ans+=hit[i];
printf("%d",ans);
}