「剰余による分類」の編集履歴(バックアップ)一覧はこちら
「剰余による分類」(2012/11/30 (金) 16:36:23) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
大学への数学 マスターオブ整数論をプログラムで解くページ。
問い8-1
10個の自然数が小さい順に並んでいる。
大きい数字-小さい数字が6の倍数になる数はいくつか?
計算量nの解法と、計算量n^2/2の解法。
#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("解法1による解=%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("解法2による解=%d\n",ans);
}
*問い8-2
mod(13n+5,11)==0となる自然数nを小さい方から3つあげよ。
#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乗しても下ふたケタの数が変わらない2桁の自然数を全て求めよ。
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までをそれぞれ12で割ったあまりのうち異なるものは何通りか?
#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);
}
大学への数学 マスターオブ整数論をプログラムで解くページ。
問い8-1
10個の自然数が小さい順に並んでいる。
大きい数字-小さい数字が6の倍数になる数はいくつか?
計算量nの解法と、計算量n^2/2の解法。
数字列が前の数の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("解法1による解=%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("解法2による解=%d\n",ans);
}
*問い8-2
mod(13n+5,11)==0となる自然数nを小さい方から3つあげよ。
#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乗しても下ふたケタの数が変わらない2桁の自然数を全て求めよ。
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までをそれぞれ12で割ったあまりのうち異なるものは何通りか?
#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);
}