Submission #4022840
Source Code Expand
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back typedef long long ll; typedef pair<int,int> ii; typedef vector<int> vi; typedef unsigned long long ull; typedef long double ld; typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds; struct NumberTheory { vector<ll> primes; vector<bool> prime; vector<ll> totient; vector<ll> sumdiv; vector<ll> bigdiv; void Sieve(ll n) { prime.assign(n+1, 1); prime[1] = false; for(ll i = 2; i <= n; i++) { if(prime[i]) { primes.pb(i); for(ll j = i*2; j <= n; j += i) { prime[j] = false; } } } } ll phi(ll x) { map<ll,ll> pf; ll num = 1; ll num2 = x; for(ll i = 0; primes[i]*primes[i] <= x; i++) { if(x%primes[i]==0) { num2/=primes[i]; num*=(primes[i]-1); } while(x%primes[i]==0) { x/=primes[i]; pf[primes[i]]++; } } if(x>1) { pf[x]++; num2/=x; num*=(x-1); } x = 1; num*=num2; return num; } int mobius(ll x) { int ans=1; for(ll i = 0; primes[i]*primes[i] <= x; i++) { int cnt=0; while(x%primes[i]==0) { x/=primes[i]; cnt++; } if(cnt>=2) return 0; if(cnt==1) ans*=-1; } if(x>1) ans*=-1; return ans; } }; const int MOD = (1e9 + 7); int add(int a, int b) { a+=b; while(a>=MOD) a-=MOD; return a; } int mult(int a, int b) { return (a*1LL*b)%MOD; } int modpow(int a, int b) { int r=1; while(b) { if(b&1) r=mult(r,a); a=mult(a,a); b>>=1; } return r; } map<int,vi> D; map<int,int> phimap; map<int,int> mobiusmap; NumberTheory nt; int phi(int x) { if(phimap.find(x)==phimap.end()) return (phimap[x]=nt.phi(x)); return phimap[x]; } int mobius(int x) { if(mobiusmap.find(x)==mobiusmap.end()) return (mobiusmap[x]=nt.mobius(x)); return mobiusmap[x]; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n,k; cin>>n>>k; nt.Sieve(100011); vector<int> divi; for(int d=1;d*d<=n;d++) { if(n%d==0) { divi.pb(d); if(d*d!=n) divi.pb(n/d); } } sort(divi.begin(),divi.end()); for(int x:divi) { for(int y:divi) { if(x%y==0) D[x].pb(y); } } int ans = 0; for(int d:divi) { //minimal period = d int res = 0; for(int v:D[d]) { res = add(res, mult(MOD+mobius(d/v),modpow(k,(v+1)/2))); } if(d%2==0) res=mult(res,modpow(2,MOD-2)); res=mult(res,d); ans=add(ans,res); } cout<<ans<<'\n'; }
Submission Info
Submission Time | |
---|---|
Task | F - Rotated Palindromes |
User | zscoder |
Language | C++14 (GCC 5.4.1) |
Score | 1000 |
Code Size | 2722 Byte |
Status | AC |
Exec Time | 36 ms |
Memory | 1280 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1000 / 1000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All | 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00.txt | AC | 2 ms | 512 KB |
0_01.txt | AC | 2 ms | 512 KB |
0_02.txt | AC | 2 ms | 512 KB |
0_03.txt | AC | 2 ms | 512 KB |
1_00.txt | AC | 2 ms | 512 KB |
1_01.txt | AC | 2 ms | 512 KB |
1_02.txt | AC | 3 ms | 512 KB |
1_03.txt | AC | 3 ms | 512 KB |
1_04.txt | AC | 2 ms | 512 KB |
1_05.txt | AC | 2 ms | 512 KB |
1_06.txt | AC | 2 ms | 512 KB |
1_07.txt | AC | 2 ms | 512 KB |
1_08.txt | AC | 3 ms | 512 KB |
1_09.txt | AC | 3 ms | 512 KB |
1_10.txt | AC | 3 ms | 512 KB |
1_11.txt | AC | 3 ms | 512 KB |
1_12.txt | AC | 2 ms | 512 KB |
1_13.txt | AC | 2 ms | 512 KB |
1_14.txt | AC | 2 ms | 512 KB |
1_15.txt | AC | 2 ms | 512 KB |
1_16.txt | AC | 36 ms | 1280 KB |
1_17.txt | AC | 36 ms | 1280 KB |
1_18.txt | AC | 36 ms | 1280 KB |
1_19.txt | AC | 36 ms | 1280 KB |
1_20.txt | AC | 30 ms | 1076 KB |
1_21.txt | AC | 30 ms | 1076 KB |
1_22.txt | AC | 30 ms | 1152 KB |
1_23.txt | AC | 30 ms | 1076 KB |
1_24.txt | AC | 2 ms | 512 KB |
1_25.txt | AC | 2 ms | 512 KB |
1_26.txt | AC | 2 ms | 512 KB |
1_27.txt | AC | 2 ms | 512 KB |
1_28.txt | AC | 2 ms | 512 KB |
1_29.txt | AC | 2 ms | 512 KB |
1_30.txt | AC | 2 ms | 512 KB |
1_31.txt | AC | 2 ms | 512 KB |