https://vjudge.net/article/752

数学训练一

LightOJ-1008

二分确定 x 使得 x\in [n^2,(n + 1)^2] . 然后模拟。

#include "iostream"
#include "algorithm"
#include "cstring"

#define int long long
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;

// const int mod = 1e9 + 7;

int rd() {
    int f = 1, val = 0; int ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

int judge(int x, int n) {
    return n <= x * x;
}

void solve() {
    int n = rd();
    int l = 1, r = 1e8;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(judge(mid, n)) r = mid;
        else l = mid + 1;
    }

    n -= (l - 1) * (l - 1);
    if(l & 1) {
        if(n <= l) printf("%lld %lld\n", l, n);
        else printf("%lld %lld\n", 2 * l - n, l);
    } else {
        if(n <= l) printf("%lld %lld\n", n, l);
        else printf("%lld %lld\n", l, 2 * l - n);
    }
}

signed main() {
    int T = rd();
    for(int i = 1; i <= T; i++) {
        printf("Case %lld: ", i);
        solve();
    }

    return 0;
}

lightoj-1010

很有意思的一点是，题目里格子是一深一浅交替排布的。 容易发现如果马放在深色格子里，那么所有的浅色格子都攻击不到。 注意特判.

#include "iostream"
#include "algorithm"
#include "cstring"

#define int long long
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;

int rd() {
    int f = 1, val = 0; int ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void solve() {
    int m = rd(), n = rd();
    if(m > n) swap(m, n);
    if(m == 1) printf("%lld\n", n);
    else if(m == 2) {
        printf("%lld\n", n / 4 * 4 + min(n % 4, 2LL) * 2);
    } else if(m == 2 && (n == 3 || n == 4)) {
        puts("4");
    } else printf("%lld\n", (m * n + 1) / 2);
}

signed main() {
    int T = rd();
    for(int i = 1; i <= T; i++) {
        printf("Case %lld: ", i);
        solve();
    }
    return 0;
}

lightoj 1020

简单博弈论。

#include "iostream"
#include "algorithm"
#include "cstring"

#define int long long
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;

int rd() {
    int f = 1, val = 0; int ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void solve() {
    int n = rd(); char name[10];
    scanf("%s", name + 1);
    if(name[1] == 'A') {
        if(n % 3 == 1) puts("Bob");
        else puts("Alice");
    } else {
        if(n % 3 == 0) puts("Alice");
        else puts("Bob");
    }
}

signed main() {
    int T = rd();
    for(int i = 1; i <= T; i++) {
        printf("Case %lld: ", i);
        solve();
    }
    return 0;
}

lightoj 1078 Integer Divisibility

如果 (n, m) = 1 可以用bsgs。 但是这题枚举就行...祝了

另外这题欠个证明，ans 一定小于 m，原因等我学了剩余类再证。

#include <cstdio>
int main()
{
    int t;
    scanf("%d", &t);
    long long Q=1; 
    while(t--)
    {
        int div, dig;
        scanf("%d%d", &div, &dig);
        int sum=dig;
        long long times=1;
        if(dig%div==0)
            times=0;
        while(sum)
        {
            sum=(sum*10+dig)%div;
            times++;
        }  
        printf("Case %lld: %lld\n", Q++, times);
    }
    return 0;
}

lightoj 1116 Ekka Dokka

#include "iostream"
#include "algorithm"
#include "cstring"

#define int long long
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;

int rd() {
    int f = 1, val = 0; int ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void solve() {
    unsigned long long w = rd();
    if(w & 1) puts("Impossible");
    else {
        unsigned long long t = (w & -w) >> 1, even = t;
        while(t) t >>= 1, w >>= 1;
        printf("%llu %llu\n", w, even << 1);
    }
}

signed main() {
    int T = rd();
    for(int i = 1; i <= T; i++) {
        printf("Case %lld: ", i);
        solve();
    }
    return 0;
}