列表

详情


NC23047. 华华给月月出题

描述

华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超,华华还给月月出了一道类似的题:

符号表示异或和,详见样例解释。
虽然月月写了个程序暴力的算出了答案,但是为了确保自己的答案没有错,希望你写个程序帮她验证一下。

输入描述

输入一个正整数N。

输出描述

输出答案Ans。

示例1

输入:

3

输出:

18

说明:

N=3时,1^3=12^3=83^3=27,异或和为18。

示例2

输入:

2005117

输出:

863466972

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

pypy3 解法, 执行用时: 1848ms, 内存消耗: 238644K, 提交时间: 2022-04-22 09:32:04

MOD = 10 ** 9 + 7

def binPow(a, b, m):
    res = 1
    while b:
        if b & 1:
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res

n = int(input())

prime = []
# is_prime = [1] * (n+1)
res = [0] * (n+1)

for i in range(2, n+1):
    if res[i] == 0:
        prime.append(i)
        res[i] = binPow(i, n, MOD)
    
    for p in prime:
        j = p * i
        if j > n:
            break
        res[j] = res[i] * res[p] % MOD
        if i % p == 0:
            break

ans = 1
for x in res[2:]:
    ans ^= x

print(ans)


C++14(g++5.4) 解法, 执行用时: 784ms, 内存消耗: 105464K, 提交时间: 2019-03-11 14:59:46

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=1.3e7+100;
const int mod=1e9+7;
int prim[N],vis[N],k[N],n;

ll qp(ll a,ll b){
	ll ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	ll ans=1,cnt=0;
	cin>>n;
	for(int i=2;i<=n;++i){
		if(!vis[i]){
			prim[cnt++]=i;
			k[i]=qp(i,n);
		}
		for(int j=0;j<cnt&&i*prim[j]<=n;++j){
			vis[i*prim[j]]=1;
			k[i*prim[j]]=1ll*k[i]*k[prim[j]]%mod;
			
		}
		ans^=k[i];
	}
	cout<<ans<<endl;
	return 0;
}

C++ 解法, 执行用时: 943ms, 内存消耗: 380K, 提交时间: 2021-06-04 19:06:09

#include<bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int n;

long long power(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main() {
    
    cin >> n;

    int res = 0;
    for (int i = 1; i <= n; i++) {
        res ^= power(i, n);
    }

    cout << res << '\n';

    return 0;
}

上一题