NC23047. 华华给月月出题
描述
输入描述
输入一个正整数N。
输出描述
输出答案Ans。
示例1
输入:
3
输出:
18
说明:
N=3时,,,,异或和为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; }