src/fps/sqrt/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	94.9%	75 / 0 / 79
Functions:	100.0%	6 / 0 / 6
Branches:	84.8%	39 / 0 / 46

    src/fps/sqrt/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../nt/residue/q/lib.hpp"
      
        #include "../inv/lib.hpp"
      
        #include "../shl/lib.hpp"
      
        #include "../shr/lib.hpp"
      
        namespace tifa_libs {
      
        template <poly_c poly_t>
      
        129
        CEXP auto sqrt_fps(poly_t p, u32 n = 0) NE {
      
          using mint = TPN poly_t::val_t;
      
        129
          std::optional<poly_t> ret;
      
          5/6auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int):
✓ Branch 0 taken 35 times.
✗ Branch 1 not taken.
auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 12 times.
auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 12 times.

        129
          if (!n) n = (u32)p.size();
      
        12554412
          cu32 cnt = u32(find_if(begin(p), begin(p) + n, [](cT_(mint) x) NE { return x.val() != 0; }) - begin(p));
      
          8/10auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const:
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 33 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const:
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 33 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const:
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 33 times.

        129
          if (cnt == n) [[unlikely]] {
      
        6
            ret.emplace(p.pre(n));
      
        6
            return ret;
      
          }
      
          8/10auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 12 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const:
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 28 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const:
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 28 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const:
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 28 times.

        123
          if (cnt & 1) return ret;
      
        108
          poly_t ans{0};
      
        108
          p = shr_fps(p, cnt);
      
          8/10auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✗ Branch 5 not taken.
✓ Branch 6 taken 12 times.
auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✗ Branch 5 not taken.
✓ Branch 6 taken 12 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const:
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 17 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const:
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 17 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const:
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 17 times.

        108
          if (auto qres = qresidue(p[0].val(), mint::mod()); !qres) return ret;
      
        75
          else ans[0] = min(qres.value(), mint::mod() - qres.value());
      
        75
          auto i2 = mint(2).inv();
      
          10/10auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int):
✓ Branch 13 taken 136 times.
✓ Branch 14 taken 12 times.
auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int):
✓ Branch 13 taken 136 times.
✓ Branch 14 taken 12 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const:
✓ Branch 13 taken 206 times.
✓ Branch 14 taken 17 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const:
✓ Branch 13 taken 206 times.
✓ Branch 14 taken 17 times.
tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const:
✓ Branch 13 taken 206 times.
✓ Branch 14 taken 17 times.

        965
          for (u32 i = 1; i < n; i *= 2) ans = (ans + p.pre(i * 2) * inv_fps(ans, i * 2)) * i2;
      
        75
          ret.emplace(shl_fps(ans.pre(n), cnt / 2));
      
        75
          return ret;
      
        108
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../nt/residue/q/lib.hpp"
4			#include "../inv/lib.hpp"
5			#include "../shl/lib.hpp"
6			#include "../shr/lib.hpp"
7
8			namespace tifa_libs {
9
10			template <poly_c poly_t>
11		129	CEXP auto sqrt_fps(poly_t p, u32 n = 0) NE {
12			using mint = TPN poly_t::val_t;
13		129	std::optional<poly_t> ret;
14	5/6 auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int): ✓ Branch 0 taken 35 times. ✗ Branch 1 not taken. auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✓ Branch 0 taken 35 times. ✓ Branch 1 taken 12 times. auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✓ Branch 0 taken 35 times. ✓ Branch 1 taken 12 times.	129	if (!n) n = (u32)p.size();
15		12554412	cu32 cnt = u32(find_if(begin(p), begin(p) + n, [](cT_(mint) x) NE { return x.val() != 0; }) - begin(p));
16	8/10 auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 12 times. auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 12 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const: ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 33 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const: ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 33 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const: ✓ Branch 0 taken 2 times. ✓ Branch 1 taken 33 times.	129	if (cnt == n) [[unlikely]] {
17		6	ret.emplace(p.pre(n));
18		6	return ret;
19			}
20	8/10 auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 12 times. auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✗ Branch 0 not taken. ✓ Branch 1 taken 12 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const: ✓ Branch 0 taken 5 times. ✓ Branch 1 taken 28 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const: ✓ Branch 0 taken 5 times. ✓ Branch 1 taken 28 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const: ✓ Branch 0 taken 5 times. ✓ Branch 1 taken 28 times.	123	if (cnt & 1) return ret;
21		108	poly_t ans{0};
22		108	p = shr_fps(p, cnt);
23	8/10 auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✗ Branch 5 not taken. ✓ Branch 6 taken 12 times. auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✗ Branch 5 not taken. ✓ Branch 6 taken 12 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const: ✓ Branch 5 taken 11 times. ✓ Branch 6 taken 17 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const: ✓ Branch 5 taken 11 times. ✓ Branch 6 taken 17 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const: ✓ Branch 5 taken 11 times. ✓ Branch 6 taken 17 times.	108	if (auto qres = qresidue(p[0].val(), mint::mod()); !qres) return ret;
24		75	else ans[0] = min(qres.value(), mint::mod() - qres.value());
25		75	auto i2 = mint(2).inv();
26	10/10 auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int): ✓ Branch 13 taken 136 times. ✓ Branch 14 taken 12 times. auto tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int): ✓ Branch 13 taken 136 times. ✓ Branch 14 taken 12 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_bs_tag<998244353ul> >) const: ✓ Branch 13 taken 206 times. ✓ Branch 14 taken 17 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms64_tag<998244353ul> >) const: ✓ Branch 13 taken 206 times. ✓ Branch 14 taken 17 times. tifa_libs::sqrt_fps<tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > > >(tifa_libs::poly_impl_::poly<tifa_libs::polyntt_impl_::cconv_ntt<tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> > > >, unsigned int)::{lambda(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >)#1}::operator()(tifa_libs::mint_impl_::mint<tifa_libs::mint_ms_tag<998244353ul> >) const: ✓ Branch 13 taken 206 times. ✓ Branch 14 taken 17 times.	965	for (u32 i = 1; i < n; i = 2) ans = (ans + p.pre(i 2) * inv_fps(ans, i * 2)) * i2;
27		75	ret.emplace(shl_fps(ans.pre(n), cnt / 2));
28		75	return ret;
29		108	}
30
31			} // namespace tifa_libs
32