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
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
AC × 4
AC × 36
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