Submission #4034178
Source Code Expand
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
typedef long double f3;
int la;
ll alp[]={2,3,5,7,11,13,17,19,23,29},a[233];
ll ch(ll x,ll y,ll p) {
x%=p, y%=p; return (x*y-ll((f3(x)*y+0.5)/p)*p+p)%p;
}
ll qp(ll x,ll y,ll p) {ll re=1;for(;y;y>>=1,x=ch(x,x,p))if(y&1)re=ch(re,x,p);return re;}
ll gcd(ll x,ll y) {return y?gcd(y,x%y):x;}
bool check(ll a,ll n,ll r,ll s) {
ll x=qp(a,r,n),lst=x;
int i;
for(i=1;i<=s;i++,lst=x) {
x=ch(x,x,n);
if(x==1&&lst!=1&&lst!=n-1) return 0;
}return x==1;
}
bool MR(ll n) {
ll r=n-1,s=0;
for(;!(r&1);r>>=1,s++) ;
int i;
for(i=0;i<8;i++) {
if(alp[i]==n) return 1;
if(!check(alp[i],n,r,s)) return 0;
}return 1;
}
ll PR(ll n,ll c) {
ll x=rand()%(n-1),y=x,p;
for(p=1;p==1;) {
x=(ch(x,x,n)+c)%n, y=(ch(y,y,n)+c)%n, y=(ch(y,y,n)+c)%n;
p=gcd(x>y?x-y:y-x,n);
}return p;
}
void solve(ll n) {
if(n<=1) return ;
if(!(n&1)) {
a[++la]=2; while(!(n&1)) n>>=1;
}
if(n<=1) return ;
if(MR(n)) {a[++la]=n; return ;}
ll t=n;
for(;t==n;t=PR(n,rand()%(n-1)));
solve(t);
while(n%t==0) n/=t;
solve(n);
}
ll n,K,mod,ans;
ll qp2(ll x,ll y) {ll re=1;x%=mod;for(;y;y>>=1,x=x*x%mod) if(y&1) re=re*x%mod; return re;}
ll g(ll x) {return qp2(K,((x+1)>>1));}
ll h(ll x) {return ((x&1)?x:(x>>1))%mod;}
void dfs(int dep,ll now,ll mud) {
if(dep==la+1) {
if(((n/now)&1)&&(!(now&1))) return ;
ans=(ans+g(n/now)*h(n/now)%mod*mud)%mod;
return ;
}
dfs(dep+1,now,mud);
mud=mud*(mod+1-a[dep]%mod)%mod;
ll nxt=now*a[dep];
for(;n%nxt==0;) {
dfs(dep+1,nxt,mud); nxt=nxt*a[dep];
}
}
int main() {
ans=0;
scanf("%lld%lld",&n,&K);
mod=1000000007;
la=0; solve(n);
sort(a+1,a+la+1); la=unique(a+1,a+la+1)-a-1;
dfs(1,1,1);
printf("%lld\n",(ans+mod)%mod);
}
Submission Info
Submission Time
2019-01-18 11:03:49+0900
Task
F - Rotated Palindromes
User
ibuki_suika
Language
C++14 (GCC 5.4.1)
Score
1000
Code Size
1853 Byte
Status
AC
Exec Time
1 ms
Memory
128 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:71:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&K);
^
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
1 ms
128 KB
0_01.txt
AC
1 ms
128 KB
0_02.txt
AC
1 ms
128 KB
0_03.txt
AC
1 ms
128 KB
1_00.txt
AC
1 ms
128 KB
1_01.txt
AC
1 ms
128 KB
1_02.txt
AC
1 ms
128 KB
1_03.txt
AC
1 ms
128 KB
1_04.txt
AC
1 ms
128 KB
1_05.txt
AC
1 ms
128 KB
1_06.txt
AC
1 ms
128 KB
1_07.txt
AC
1 ms
128 KB
1_08.txt
AC
1 ms
128 KB
1_09.txt
AC
1 ms
128 KB
1_10.txt
AC
1 ms
128 KB
1_11.txt
AC
1 ms
128 KB
1_12.txt
AC
1 ms
128 KB
1_13.txt
AC
1 ms
128 KB
1_14.txt
AC
1 ms
128 KB
1_15.txt
AC
1 ms
128 KB
1_16.txt
AC
1 ms
128 KB
1_17.txt
AC
1 ms
128 KB
1_18.txt
AC
1 ms
128 KB
1_19.txt
AC
1 ms
128 KB
1_20.txt
AC
1 ms
128 KB
1_21.txt
AC
1 ms
128 KB
1_22.txt
AC
1 ms
128 KB
1_23.txt
AC
1 ms
128 KB
1_24.txt
AC
1 ms
128 KB
1_25.txt
AC
1 ms
128 KB
1_26.txt
AC
1 ms
128 KB
1_27.txt
AC
1 ms
128 KB
1_28.txt
AC
1 ms
128 KB
1_29.txt
AC
1 ms
128 KB
1_30.txt
AC
1 ms
128 KB
1_31.txt
AC
1 ms
128 KB