UVa 10673 - Play with Floor and Ceil

#数学 #数论
Published on 2016-03-01

题目地址

描述

给定 x,k(1≤x,k≤108)x, k(1\le x, k\le10^8)，求一组使下列方程成立的 p,qp, q。

x=p⌊xk⌋+q⌈xk⌉x = p\left\lfloor\frac{x}{k}\right\rfloor + q\left\lceil\frac{x}{k}\right\rceil

样例输入

3
5 2
40 2
24444 6

样例输出

1 1
1 1
0 6

分析

上下取整总有点让人恶心，因为总有些裹不清楚的味道，不妨换成余数式子。
设 x=mk+d(0≤d≤k)x = mk + d(0\le d\le k)。
如果 d=0d = 0，令 p=0,q=kp = 0, q = k 即可满足等式。
如果 ，原方程可化为：

注意到常数项，可令 q=dq = d，则

m×k=m×(p+d)m \times k = m \times (p + d)

当 p=k−dp = k - d 时上式成立（我想我懒得讨论 m=0m = 0 的情况了），由于 0≤d<k0\le d < k，所以 pp 是一个正整数。
综合一下：
如果 k∣xk \mid x，解为：
如果 ，解为：

代码

//  Created by Sengxian on 3/1/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  UVa 10673 数论
#include <cctype>
#include <cstdio>
using namespace std;

inline int ReadInt() {
    int n = 0, ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

int main() {
    int x, k, caseNum = ReadInt();
    while(caseNum--) {
        x = ReadInt(), k = ReadInt();
        if(x % k == 0) printf("0 %d\n", k);
        else printf("%d %d\n", k - x % k, x % k);
    }
    return 0;
}

附加输入

10
45 14
523 23
123 31
2934 26
1334 1613
1456 1551413
767747 475204
5256256 2525253
12313154 78149147
14890144 16101

附加输出

3 9
6 17
1 30
4 22
0 1334
0 1456
1 383873
2 1752084
0 12313154
506 15592
UVa 10692 - Huge Mods