フェルマーの小定理とmod、二項係数など（仮・メモ）

10^9+7で割ったあまり問題

qiita.com

フェルマーの小定理

qiita.com

整数論テクニック集

kirika-comp.hatenablog.com

042-Dについて

二項係数

drken1215.hatenablog.com

nCr mod m
https://w.atwiki.jp/uwicoder/pages/2118.html

逆元の求め方

#include <stdio.h>

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main(void){
    // mod. 13 での逆元を求めてみる
    int i;
    for (i = 1; i < 13; ++i) {
        printf("%d's inv: %d\n",i,modinv(i,13));
    }

    return 0;
}

AtCoder Beginner Contest 062 by C

AtCoder Beginner Contest 062　について
C言語での回答

atcoder.jp

できたもの
A
B

できなかったもの
C
D

問題A

#include <stdio.h>

int main(void){
    int x,y,i,j;
    scanf("%d %d", &x,&y);

    if(x==2||y==2){
        printf("No");
        return 0;
    }
    else if(x==1||x==3||x==5||x==7||x==8||x==10||x==12){
        if(y==1||y==3||y==5||y==7||y==8||y==10||y==12){
            printf("Yes");
            return 0;
        }
        printf("No");
        return 0;
    }
    else if(x==4||x==6||x==9||x==11){
        if(y==4||y==6||y==9||y==11){
            printf("Yes");
            return 0;
        }
            printf("No");
            return 0;
    }

    
    return 0;
}

最初配列に値を入れて、それで参照して～とかやってましたが、数も少ないので論理和直書きで。

問題B

#include <stdio.h>

int main(void){
    int h,w,i,j;
    char a[101][101];
    scanf("%d %d", &h,&w);

    for(i=0;i<h;i++){
        scanf("%s", a[i]);
    }


    for(i=0;i<w+2;i++){
        printf("#");
    }
    printf("\n");
    for(i=0;i<h;i++){
        printf("#");
        for(j=0;j<w;j++){
            printf("%c", a[i][j]);
        }
        printf("#\n");
    }
    for(i=0;i<w+2;i++){
        printf("#");
    }
    
    return 0;
}

受け取った画像（文字列）の周り１ピクセルを#で囲います。
元の文字列については前後に#を付けます（abc → #abc#）
ループの前と後に#だけの行を出力すれば無事囲えます。

問題C

#include <stdio.h>

const long long inf = (long long)1 << 60;

long long H,W;

long long max(long long a,long long b){
    return a > b ? a : b;
}

long long min(long long a,long long b){
    return a > b ? b : a;
}

long long f(long long a, long long b, long long c){
    long long ma = max(a,max(b,c));
    long long mi = min(a,min(b,c));
    return ma - mi;
}

long long solA(){
    long long res = inf;
    if(2<H){
        long long h = H/3;
        if(H%3==0){
            return 0;
        }
        res = min(res,W);
    }

    if(2<W){
        if(W%3==0){
            return 0;
        }
        res = min(res,H);
    }
    return res;
}

long long solB(){
    long long res = inf;
    int i,j;
    for(i=1;i<W;i++){
        long long xx = i;
        long long b = H/2;
        res = min(res, f(xx*b,xx*(H-b),(W-xx)*H));
    }
    for(j=1;j<H;j++){
        long long yy = j;
        long long b = W/2;
        res = min(res, f(yy*b,yy*(W-b),(H-yy)*W));
    }
    return res;
}

int main(void){
    scanf("%lld %lld", &H,&W);
    long long ans = min(solA(),solB());
    printf("%lld\n", ans);
    return 0;
}

3等分する方法は上の4通り（解説を元にプログラムに合わせて書きました）
関数solAでは上2つのやり方で分けた時に差が小さい方の値を、関数solBでは下2つのやり方で分けた時に差が小さい方を返します。
メイン関数でその返り値を比較し、小さい方が4通りの中で最も小さくなる値です。
C言語にはSTL関数がないのでプログラムの先頭に自分で作ってます。

解けなかった原因

方針が思い付かなかった。

問題D

AtCoder Beginner Contest 058 by C

AtCoder Beginner Contest 058　について
C言語での回答

atcoder.jp

できたもの
A
B

できなかったもの
C
D

問題A

#include <stdio.h>

int main(void){
    int a,b,c;
    scanf("%d %d %d", &a,&b,&c);

    if(b-a==c-b){
        printf("YES");
    }
    else{
        printf("NO");
    }
    
    return 0;
}

複数条件がいるかと思いましたが、問題文中の例から差がマイナスであってもa、bとb、cの差が合えさえすればいいみたいだったので必要なのは　b-a==c-b　のみです。

問題B

#include <stdio.h>
#include <string.h>

int main(void){
    char o[51],e[51];
    int i;
    scanf("%s", o);
    scanf("%s", e);
    int size_o = strlen(o);
    int size_e = strlen(e);

    if(size_o==size_e){
        for(i=0;i<size_o;i++){
            printf("%c", o[i]);
            printf("%c", e[i]);
        }
    }
    else{
        for(i=0;i<size_e;i++){
            printf("%c", o[i]);
            printf("%c", e[i]);
        }
        printf("%c", o[size_o-1]);
    }
    
    return 0;
}

奇数番目と偶数番目で配列が分かれているので、パスワードの先頭から奇数[0]→偶数[0]→奇数[1]→偶数[1]......と表示していきます。
パスワードの長さが奇数なら偶数[n]→奇数[n+1]、偶数なら奇数[n]→偶数[n]となるので条件に合わせてそれぞれ分け、奇数の場合にはfor文で交互に表示した後最後に奇数の最後を出力するようにしました。

問題C

#include <stdio.h>
#include <string.h>

int main(void){
    int n,i,j;
    char s[51],sa[51];
    int count[26]={0};
    scanf("%d", &n);

    scanf("%s", sa);
    int size = strlen(sa);
    for(i=0;i<size;i++){
        count[(int)sa[i]-97]++;  
    }

    for(i=1;i<n;i++){
        int count_tmp[26] = {0};
        scanf("%s", s);
        size = strlen(s);
        for(j=0;j<size;j++){
            count_tmp[(int)s[j]-97]++;
        }
        for(j=0;j<26;j++){
            if(count_tmp[j]<count[j]){
                count[j] = count_tmp[j];
            }
        }      
    }

    for(i=0;i<26;i++){
        if(count[i]==0){
            continue;
        }
        for(j=0;j<count[i];j++){
            printf("%c", i+97);
        }
    }

    return 0;
}

各配列において、アルファベットの数をカウントし、その数が最小の数ほど出力します。
カウントの仕方として、アルファベットを数値（文字コード）に変換しています。
aの文字コードは97、bの文字コードは98・・・zの文字コードは122なので、97を引くと0,1...25となります。
まずアルファベットの数をカウントする要素26の配列count[26]を0で初期化、
このままでは比較しても全て0になってしまうので、ループの外でS1だけアルファベットの数をカウントして配列に加算しています。
S2からSnまではループ。それぞれのSでアルファベットの数をカウント（count_tmp[26]）、coutn[]とそれぞれの要素で数を比較し、小さい方をcountに代入。
出力時には、countが0のアルファベットはスキップ、0以外であればカウントの数ほどループで出力。
97を引いたので出力時には足すことを忘れずに。

解けなかった原因

方針の立て方が良くなかった

問題D

まだ

AtCoder Beginner Contest 059 by C

AtCoder Beginner Contest 059　について
C言語での回答

atcoder.jp

できたもの
A
B

できなかったもの
C
D

問題A

#include <stdio.h>
#include <ctype.h>

int main(void){
    char a[11],b[11],c[11];
    scanf("%s %s %s", a, b, c);
    
    printf("%c%c%c", toupper(a[0]),toupper(b[0]),toupper(c[0]));

    return 0;
}

問題B

#include <stdio.h>
#include <string.h>

int main(void){
    char a[101],b[101];
    int i;
    scanf("%s", a);
    scanf("%s", b);
    int size_a = strlen(a);
    int size_b = strlen(b);

    int judge = 0;
    if(size_a>size_b){
        judge = 1;
    }
    else if(size_a<size_b){
        judge = -1;
    }
    else{
        for(i=0;i<size_a;i++){
            if(a[i]>b[i]){
                judge = 1;
                break;
            }
            else if(a[i]<b[i]){
                judge = -1;
                break;
            }
        }
    }

    if(judge==1){
        printf("GREATER");
    }
    else if(judge==-1){
        printf("LESS");
    }
    else{
        printf("EQUAL");
    }

    
    return 0;
}

10の100乗なのでlong long型には収まりません。
double型にすれば収まるのでそうして数値として扱ってもいいみたいです。

今回は文字列としてそれぞれ数値を取得。桁数が違う＝配列の要素数が違えば、桁数が多い方が大きく、
桁数が同じ場合には、より大きな位（要素0）から順番に比較し、異なる部分があれば大小関係を見て結果を出力。

問題C

一旦他の方を参考に作成↓

#include <stdio.h>

int main(void){
    int n,i;
    scanf("%d", &n);
    int a;

    long long kisum = 0, gusum = 0, kians = 0, guans = 0;

    for(i=0;i<n;i++){
        scanf("%d", &a);

        kisum += a;
        gusum += a;

        if(i%2==0){
            if(gusum <= 0){
                printf("1\n");
                guans = guans - gusum + 1;
                gusum = 1;
            }
            if(kisum >= 0){
                printf("2\n");
                kians = kians + kisum +1;
                kisum = -1;
            }
        }
        else{
            if(gusum >= 0){
                printf("3\n");
                guans = guans + gusum + 1;
                gusum = -1;
            }
            if(kisum <= 0){
                printf("4\n");
                kians = kians - kisum + 1;
                kisum = 1;
            }
        }
        printf("%lld %lld\n", kisum,gusum);
    }

    if(kians > guans){
        printf("%lld\n", guans);
    }
    else{
        printf("%lld\n", kians);
    }
    
    return 0;
}

問題D

まだ

AtCoder Beginner Contest 056 by C

AtCoder Beginner Contest 056　について
C言語での回答

atcoder.jp

できたもの
A
B
C

できなかったもの
D

問題A

#include <stdio.h>

int main(void){
    char a,b;
    scanf("%c %c", &a, &b);

    if(a=='H'&&b=='H'){
        printf("H");
    }
    else if(a=='H'&&b=='D'){
        printf("D");
    }
    else if(a=='D'&&b=='H'){
        printf("D");
    }
    else{
        printf("H");
    }
    
    return 0;
}

HとDの組み合わせは4通り。それぞれの条件に合わせてHかDを出力する。

問題B

#include <stdio.h>

int main(void){
    int w,a,b;
    scanf("%d %d %d", &w, &a, &b);

    int move;
    if(a<b){
        if(b<a+w){
            move = 0;
        }
        else{
            move = b - (a + w);
        }
    }
    else{
        if(a<b+w){
            move = 0;
        }
        else{
            move = a - (b + w);
        } 
    }

    printf("%d", move);

    
    return 0;
}

離れてる距離分移動する。
重なっていたら移動は0。
aとbの大小関係に注意。

問題C

#include <stdio.h>

int main(void) {
    long long x;
    int i;
    scanf("%lld", &x);

    long long sum = 0;
    for(i=1;i<x+1;i++){
        sum += i; 
        printf("%d\n", sum);
        if(sum >= x){
            printf("%d", i);
            break;
        }
    }

    return 0;
}

足し合わせて値を超えた場合が最短。
値は超えてしまっても、Xとの差はそこまでに足した値のどれかなのでそれを引けばちゃんとたどり着けます。

問題D

まだ

解説
https://img.atcoder.jp/arc070/editorial.pdf
公式

https://physics0523.hatenablog.com/entry/2019/01/01/182437
（C言語）

https://blog.hamayanhamayan.com/entry/2017/03/19/085701

https://atcoder.jp/contests/arc070/submissions/1172088
解答例（C＋＋）

解答例

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}

int main(void){
    int i,j,n,k,a[8192];
    bool fl[8192]={0};
    int st,fi,te;
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }

    qsort(a,n,sizeof(int),sortfncsj);

    st=0;fi=n-1;
    while(st<=fi){
        te=(st+fi)/2;
        if(a[te]>=k){
            fi=te-1;
            continue;
        }
        for(i=1;i<k;i++){
            fl[i]=0;
        }
        fl[0]=1;
        for(i=0;i<n;i++){
            if(i==te){
                continue;
            }
            for(j=k-1-a[i];j>=0;j--){
                if(fl[j]==1){
                    fl[j+a[i]]=1;
                }
            }
        }
        for(i=k-a[te];i<k;i++){
            if(fl[i]==1){
                fi=te-1;
                break;
            }
            if(i==k-1){
                st=te+1;
            }
        }
    }
    printf("%d\n",st);
    return 0;
}

AtCoder Beginner Contest 070 by C

AtCoder Beginner Contest 070 について
C言語での回答

atcoder.jp

今回は調子がいいぞ！

できたもの
A
B
C

できなかったもの
D

問題A

#include <stdio.h>

int main(void){
    char n[3];
    scanf("%s", &n);

    if(n[0]==n[2]){
        printf("Yes");
    }
    else{
        printf("No");
    }

    return 0;
}

数字って書いてるけど1桁目と3桁目を比較したいんだから文字列として受け取ってやり、
str[0]とstr[2]で比較してやればおしまい。

問題B

#include <stdio.h>

int main(void){
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);

    if(c>b||d<a){
        printf("0");
    }
    else if(a<=c&&b>=d){
        printf("%d", d-c);
    }
    else if(a<=c&&b<d){
        printf("%d", b-c);
    }
    else if(a>=c&&b>=d){
        printf("%d", d-a);
    }
    else if(a>=c&&b<d){
        printf("%d", b-a);
    }


    return 0;
}

分岐条件に注意。cがaより後とは限らないのだ。
bとdの=に関しては逆にしてても同じだと思います。

問題C

#include <stdio.h>

long long gcd(long long a, long long b){
    if(b==0){
        return a;
    }
    else{
        return gcd(b, a%b);
    }
}

long long lcm2(long long a, long long b){
    long long d = gcd(a,b);
    return a/d * b;
}

int main(void){
    int n,i;
    long long t[101];
    scanf("%d", &n);

    for(i=0;i<n;i++){
        scanf("%lld", &t[i]);
    }

    long long l = t[0];
    for(i=0;i<n-1;i++){
        l = lcm2(l,t[i+1]);
    }

    printf("%lld", l);

    return 0;
}

最小公倍数を求めればOK
分からなかったのでアルゴリズムを調べました。
こちらのサイトより
https://algo-logic.info/lcm-of-array/

問題D

まだ

途中↓

#include <stdio.h>

#define num_max 100010

long long depth[num_max];

typedef struct {
    int To;
    long long Cost;
}EDGE;

EDGE tree[300030];

//頂点vから頂点Kまでの最短距離
void dfs(int v, int p, long long d){
    int i;
    depth[v] = d;
    for(i=tree[v].To;i!=-1;i++){ //<-forの範囲どうなの？
        if(tree[i].To==p){
            continue;
        }
        dfs(tree[i].To, v, d + tree[i].Cost);
    }
}

int main(void){
    int n,q,k,i;
    scanf("%d", &n);
    int a,b;
    long long c;
    int x, y;

    for(i=0;i<n-1;i++){
        scanf("%d %d %lld", &a, &b, &c);
        a--, b--;
        tree[a].To = b;
        tree[a].Cost = c;
        tree[b].To = a;
        tree[b].Cost = c;
    }

    scanf("%d %d", &q, &k);
    k--;

    dfs(k, -1, 0);

    //頂点Kからxまでとyまでの和
    for(i=0;i<q;i++){
        scanf("%d %d", &x, &y);
        x--,y--;
        printf("%lld", depth[x]+depth[y]);
    }


    
    return 0;
}

解説：
https://img.atcoder.jp/abc070/editorial.pdf

C++のコードをCに書き換えようとしているところですが、関数のループ条件がわかりません

AtCoder Beginner Contest 054 by C

AtCoder Beginner Contest 054　について
C言語での回答

atcoder.jp

できたもの
A
B

できなかったもの
C
D

Bはごり押しが強い気がする

問題A

#include <stdio.h>

int main(void){
    int a,b;
    scanf("%d %d", &a,&b);
    if(a==b){
        printf("Draw");
    }
    else if(a!=1&&b!=1){
        if(a>b){
            printf("Alice");
        }
        else{
            printf("Bob");
        }
    }
    else{
        if(a==1){
            printf("Alice");
        }
        else{
            printf("Bob");
        }
    }
    
    return 0;
}

・値が何であろうと等しければdraw
・1以外は値の大きい方が勝ちなのでどっちが大きいかで条件分岐
・1なら1以外のすべてに勝てるのでそれぞれ1の時で条件分岐

問題B

#include <stdio.h>

int i,j;
char a[51][51], b[51][51];

int check(int m){
    int aa,bb;
    int count = 0;
    for(aa=0;aa<m;aa++){
        for(bb=0;bb<m;bb++){
            if(a[i+aa][j+bb]!=b[aa][bb]){
                count++;
            }
        }
    }
    if(count>0){
        return 1;
    }
    else{
        return 0;
    }
}

int main(void){
    int n,m;
    scanf("%d %d", &n,&m);

    for(i=0;i<n;i++){
            scanf("%s", a[i]);
    }

    for(i=0;i<m;i++){
            scanf("%s", b[i]);
    }

    //b[0][0]と一致するマスがあるか探す
    int match;
    int count = 0;
    int count2 = 0;
    int max = n-m+1;
    for(i=0;i<max;i++){
        for(j=0;j<max;j++){
            if(a[i][j]==b[0][0]){
                count++;
                match = check(m);
                if(match==0){
                    count2++;
                }
            }
        }
    }
    

    if(count==0){
        printf("No");
    }
    else if(count>0&&count2==0){
        printf("No");
    }
    else{
        printf("Yes");
    }

    
    return 0;
}

まずa,bそれぞれの2次元配列に画像の記号1文字ずつをいれます。
そうすることで一致するかどうか判定できます。
n×nの中にm×mが存在するかどうかを調べるのがcheck関数です。
b[0][0]と一致したマスからmの正方形を調べ、全て一致したら0を、1つでも違えば1を返します。
0が返って来た時だけcount2++し、count2が0でなければ1つ以上存在します
またb[0][0]と一致したマスがあればcount++、そもそもなければcount=0のままで条件分岐

解説を見るともっと簡潔に書けるようなのでまた後日。

問題C

#include <stdio.h>
#include <stdbool.h>

#define nmax 8
//隣接行列。つながっていればtrue、つながってなければfalse
bool graph [nmax][nmax];

int dfs(int v, int N, bool visited[nmax]){

    //すべての頂点を訪れたかどうか。訪れていればtrue。まだならfalse
    bool all_visited = true;

    for(int i=0;i<N;i++){
        //iを訪れていたらtrue
        if(visited[i]==false){
            //一つでも訪れてなければfalse
            all_visited = false;
        }
    }

    if(all_visited){
        return 1;
    }
    int ret = 0;

    for(int i=0;i<N;i++){
        //つながっているか。つながってなければcontinue
        if(graph[v][i]==false){
            continue;
        }
        //訪れたことがあるか。あれば（true）continue
        if(visited[i]){
            continue;
        }

        visited[i] = true;
        //次の頂点へ向けて再帰
        ret += dfs(i,N,visited);
        //一番奥までたどり着いたら戻る。終点までたどり着いた場合のみret++でカウント
        //iを訪れてないことにしてi+1の頂点へforループ
        visited[i] = false;
    }

    return ret;
    
}

int main(void){
    int n,m,i,a,b;
    scanf("%d %d", &n, &m);

    for(i=0;i<m;i++){
        scanf("%d %d", &a, &b);
        //つながっているのでtrueを入れる
        graph[a-1][b-1] = graph[b-1][a-1] = true;
    }

    //訪れた場所。訪れたらTrue
    bool visited[nmax];
    for(i=0;i<n;i++){
        visited[i] = false;
    }

    //スタート地点は訪れてるのでtrue
    visited[0] = true;
    printf("%d\n", dfs(0,n,visited));

    
    return 0;
}

無向グラフであること、頂点の数が最大8と少ないことから
隣接行列を使うかなとは思いました。思っただけで終わりましたが。

深さ優先探索によって始点から終点まですべての頂点を一度だけ通ってたどり着けるか、
再帰で求めます。

コードの中にコメント細かく入れました。
頭よすぎて自分じゃこんなのまだ思いつけそうにないです……

問題D

まだ

余談

グラフに関する面白いサイト（記事）
https://qiita.com/maskot1977/items/e1819b7a1053eb9f7d61