P1000-完全平方数

我们把一个数用如下形式表示 =
显然一个完全平方数的展开式 在mod 意义下 含有 () 的项都为0
因此我们只用考虑后三位 即枚举1000以内的数的平方 记录下取模后的结果
时间复杂度

原意是想出成T组数据，因此打表做可以做到查询

bool solve(int x) {
    // write code here
    int vis[1005];
    for(int i = 0; i < 1000; i++) vis[i] = 0;
    for(int i = 0; i < 1000; i++) vis[i * i % 1000]++;
    if(vis[x]) return true;
    else return false;
}

对于完全平方数，其最低位必定为{0, 1, 4, 9, 6, 5}, 可从最低位开始dfs, 可做到

int a[10] = {0, 1, 4, 9, 6, 5, 6, 9, 4, 1};
int num[5];
bool f = false;
void dfs(int now, int add, int zero) {
    for(int i = 0; i < 10; i++) {
        if(now == 0 && a[i] == num[0]) dfs(1, i * i / 10, i);
        if(now == 1 && (2 * zero * i + add) % 10 == num[1]) dfs(2, ((2 * zero * i + add) / 10 + a[i]) % 10, zero);
        if(now == 2 && (2 * i * zero + add) % 10 == num[2]) f = true;
    }
}
bool solve(int x) {
    for(int i = 0; i < 3; i++) {
        num[i] = x % 10;
        x /= 10;
    }
    dfs(0, 0, 0);

    if(f) return true;
    else return false;
}